﻿#define _CRT_SECURE_NO_WARNINGS
//#include <stdio.h>
#include<iostream>
using namespace std;
#include<vector>
//经此一役小红所向无敌 ***不使用模拟  这里模拟会不够  所以采用数学方法进行计算
//int main()
//{
//    long long a, b, x, y;
//    cin >> a >> b >> x >> y;
//    long long n = min(b / x, y / a);
//    long long sum = n * (a + x);
//    b -= x * n;
//    y -= a * n;
//    if (b > 0 && y > 0)
//    {
//        b -= x;
//        y -= a;
//        sum += a + x;
//    }
//
//
//    if (b > 0 || y > 0)
//    {
//        sum += 10 * (b > 0 ? a : x);
//    }
//    cout << sum << endl;
//    return 0;
//}

//连续子数组的最大和  线性dp问题 *****
//#include <iostream>
//using namespace std;
//#include<vector>
//int dp[200100] = { 0 };
//int main() {
//    int n;
//    cin >> n;
//    vector<int>v(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v[i];
//    }
//    int maxx = -110;
//    for (int i = 1; i <= n; i++)
//    {
//        dp[i] = max(dp[i - 1], 0) + v[i - 1];
//        maxx = max(dp[i], maxx);
//    }
//
//    cout << maxx << endl;
//    return 0;
//}

//非对称之美
// vector<bool> haha(m.size()) ;
//#include<iostream>
//using namespace std;
//#include<vector>
//int main()
//{
//    vector<vector<int> > m = { {1,1,0,0 }, { 1,1,1,0 }, { 0,1,1,0 }, { 0,0,0,1 }};
//    vector<bool> haha(m.size());
//    for (int i = 0; i < m.size(); i++)
//    {
//        for (int j = 0; j < i; j++)
//        {
//            if (m[i][j] == 1)
//            {
//                haha[i] = true;
//                haha[j] = true;
//            }
//        }
//
//    }
//    int num = 0;
//    for (int i = 0; i < haha.size();i++ )
//    {
//        if (haha[i] == true)
//        {
//            num++;
//            while (haha[i] == true)
//            {
//                i++;
//            }
//
//        }
//        if (haha[i] == false)
//            num++;
//    }
//    cout << num;
//    return 0;
//}

//bool check[25] = { 0 };
//vector<vector<int>> ret;
//vector<int> path;
//int main()
//{
//    int n, k;
//    cin >> n >> k;
//    dfs(n, k, 1);
//
//    for (auto e : ret)
//    {
//        for (auto ch : e)
//            cout << ch << " ";
//        cout << endl;
//    }
//    return 0;
//}
//
//void dfs(int n, int k, int pos)
//{
//    if (path.size() == k)
//    {
//        ret.push_back(path);
//        return;
//    }
//    for (int i = pos; i <= n; i++)
//    {
//        if (check[i] == false)
//        {
//            check[i] = true;
//            path.push_back(i);
//            dfs(n, k, pos + 1);
//            path.pop_back();
//            check[i] = false;
//        }
//    }
//}




#include <iostream>
using namespace std;
#include<vector>
//vector<vector<char>> vv;
//int dx[4] = { 0,0,1,-1 };
//int dy[4] = { 1,-1,0,0 };
//bool vis[1111][1111] = { 0 };
//int minn = 100000000;
//void dfs(int x, int y, int x2, int y2, int num)
//{
//    if (x == x2 && y == y2)
//    {
//        minn = min(minn, num);
//        return;
//
//    }
//
//    for (int i = 0; i < 4; i++)
//    {
//        int xx = dx[i] + x; int yy = dy[i] + y;
//        if (xx >= 0 && xx < vv.size() && yy >= 0 && yy < vv[0].size() && !vis[xx][yy] && vv[xx][yy] != '*')
//        {
//            vis[xx][yy] = true;
//            dfs(xx, yy, x2, y2, num + 1);
//            vis[xx][yy] = false;
//        }
//    }
//}
//int main() {
//    int a, b, x1, y1, x2, y2;
//    cin >> a >> b >> x1 >> y1 >> x2 >> y2;
//    vv = vector<vector<char>>(a, vector<char>(b));
//    for (int i = 0; i < a; i++)
//    {
//        for (int j = 0; j < b; j++)
//        {
//            cin >> vv[i][j];
//        }
//    }
//
//    dfs(x1 - 1, y1 - 1, x2 - 1, y2 - 1, 0);
//
//    cout << minn << endl;
//    return 0;
//}

//int dp[101][101] = { 0 };
//int main() {
//    int m; int n;
//    cin >> m >> n;
//
//    for (int i = 1; i <= m; i++)
//        for (int j = 1; j <= n; j++)
//        {
//            if (i == 1 && j == 1)
//                dp[i][j] = 1;
//            else
//                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
//        }
//    cout <<dp[m][n]<< endl;
//    return 0;
//}

//int main() {
//    vector<int> nums = { 0,1,0,3,2,3 };
//    int n = nums.size();
//    vector<int> dp(n, 1);
//    int ret = 0;
//    for (int i = n - 1; i >= 0; i--)
//    {
//        for (int j = i + 1; j < n; j++)
//        {
//            if (nums[i] < nums[j])
//                dp[i] = max(dp[j] + 1, dp[i]);
//        }
//        ret = max(ret, dp[i]);
//    }
//    cout << ret << endl;
//    return 0;
//}

//#include <climits>
//#include <iostream>
//using namespace std;
//#include<vector>
//#include<algorithm>
//int maxx = 0;
//int countt = 0;
//int target;
//int sum = 0;
//void dfs(vector<int>& v, int pos)
//{
//     if (target <= sum)
//    {
//        maxx = max(countt-1, maxx);
//        return;
//    }
//    for (int i = pos; i < v.size(); i++)
//    {
//        countt++;
//        sum += v[pos];
//        v[pos] *= 2;
//        dfs(v, i);
//        v[pos] /= 2;
//        sum -= v[pos];
//        countt--;
//    }
//}
//int main() {
//    int n, k;
//    cin >> n >> k;
//    target = k;
//    vector<int> v(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v[i];
//    }
//    sort(v.begin(), v.end());
//    dfs(v, 0);
//    cout << maxx << endl;
//    return 0;
//}


//#include <climits>
//#include <iostream>
//using namespace std;
//#include<vector>
//int dx[4] = { 0,0,1,-1 };
//int dy[4] = { 1,-1,0,0 };
//bool vis[33][33];
//int ret1 = 0; int minret = INT_MAX;   int path = 0;
//void dfs(vector<vector<char>>& v, int x, int y)
//{
//    if (v[x][y] == 'e')
//    {
//        ret1++;
//        int minret = min(minret, path);
//        return;
//    }
//    for (int i = 0; i < 4; i++)
//    {
//        int xx = dx[i] + x;  int yy = dy[i] + y;
//        if (xx >= 0 && xx < v.size() && yy >= 0 && yy < v[0].size() && !vis[xx][yy] && v[xx][yy] != '*')
//        {
//            path++;
//            vis[xx][yy] = true;
//            dfs(v, xx, yy);
//            vis[xx][yy] = false;
//            path--;
//        }
//    }
//}
//int main() {
//    int a, b;
//    cin >> a >> b;
//
//    vector<vector<char>> v;
//    v = vector<vector<char>>(a, vector<char>(b));
//    for (int i = 0; i < a; i++)
//    {
//        for (int j = 0; j < b; j++)
//        {
//            cin >> v[i][j];
//        }
//    }
//
//    for (int i = 0; i < a; i++)
//    {
//        for (int j = 0; j < b; j++)
//        {
//            if (v[i][j] == 'k')
//            {
//                dfs(v, i, j);
//            }
//        }
//    }
//
//
//    cout << ret1 << " " << minret << endl;
//    return 0;
//}

//#include <iostream>
//using namespace std;
//#include<vector>
//int dfs(vector<int>& v)
//{
//    vector<int> vv; vv.push_back(0);
//    for (int i = 1; i < v.size(); i++)
//    {
//        if (i % 2 == 0)
//            vv.push_back(v[i]);
//    }
//
//    swap(v, vv);
//    return v.size();
//}
//bool vis[1111] = { 0 };
//int main() {
//    int n;
//    cin >> n;
//    vector<int>v;
//    v.push_back(0);
//    for (int i = 0; i <= n; i++)
//    {
//        v.push_back(i);
//    }
//
//
//    while (dfs(v) != 2)
//    {
//        ;
//    }
//
//
//    cout << v[1] << endl;
//    return 0;
//}


#include <iostream>
using namespace std;

//int main() {
//    int hh[10] = { 0 };
//    int a;
//    cin >> a;
//    while (a)
//    {
//        hh[a % 10]++;
//        a /= 10;
//    }
//
//    for (int i = 9; i > 0; i++)
//    {
//        if (hh[i] != 0)
//        {
//            cout << i;
//        }
//    }
//    return 0;
//}

//int main()
//{ 
//    int numRows;
//    cin >> numRows;
//    string s;
//    cin >> s;
//    vector<vector<char>> ret(numRows);
//    int n = numRows - 1;
//    int m = 0;
//    for (int i = 0; i < ret.size(); i++)
//    {
//        ret[i].resize(s.size());
//    }
//    for (int i = 0; i < s.size(); i++)
//    {
//        if (m >= s.size()) break;
//        if (i % n == 0)
//            for (int j = 0; j < ret.size(); j++)
//            {
//                if (m >= s.size()) break;
//                ret[j][i] = s[m++];
//            }
//
//        else
//        {
//            for (int j = ret.size() - 2; j > 0; )
//            {
//                if (m >= s.size())  break;
//                ret[j--][i++] = s[m++];
//            }
//            i--;
//        }
//
//
//    }
//
//    for (auto e : ret)
//    {
//        for (auto h : e)
//            cout << h << "  ";
//        cout << endl;
//    }
//    return 0;
//}

//#include<unordered_map>
//
//int main()
//{
//    string croakOfFrogs;
//    cin >> croakOfFrogs;
//    unordered_map<char, int> hh;
//    for (auto e : croakOfFrogs)
//    {
//        if (e == 'c')
//        {
//            if (hh['k'] != 0)  hh['k']--;
//            hh[e]++;
//        }
//        else  if (e == 'r')
//        {
//            if (hh['c'] != 0)
//            {
//                hh['c']--;  hh[e]++;
//            }
//            else return -1;
//        }
//        else if (e == 'o')
//        {
//            if (hh['r'] != 0)
//            {
//                hh['r']--;  hh[e]++;
//            }
//            else return -1;
//        }
//        else if (e == 'a')
//        {
//            if (hh['o'] != 0)
//            {
//                hh['o']--; hh[e]++;
//            }
//            else return -1;
//        }
//        else if (e == 'k')
//        {
//            if (hh['a'])
//            {
//                hh['a']--; hh[e]++;
//            }
//            else return -1;
//        }
//
//
//    }
//
//    return  hh['k'];
//    return 0;
//}


/*int main()
{ 
    vector<int> nums = {1,3,4,2,2 };
    int i = 0;
    int fast = nums[nums[i]]; int slow = nums[i];
    while (fast != slow)
    {
        slow = nums[slow];
        fast = nums[nums[fast]];
    }
    fast = i;
    while (fast != slow)
    {
        fast = nums[fast];
        slow = nums[slow];
    }

    cout << slow << endl;
	return 0;
                                */   

//#include <iostream>
//using namespace std;
//#include<vector>
//int main() {
//    int n, m, q;
//    cin >> n >> m >> q;
//    vector<vector<int>> dp(n + 1);
//
//    vector<vector<int>> vv(n);
//    for (int i = 0; i < n; i++)
//        vv[i].resize(m);
//    for (int i = 0; i < n + 1; i++)
//        dp[i].resize(m + 1);
//
//    for (int i = 0; i < n; i++)
//        for (int j = 0; j < m; j++)
//            cin >> vv[i][j];
//
//    for (int i = 1; i < n + 1; i++)
//        for (int j = 1; j < m + 1; j++)
//            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + vv[i-1][j-1];
//
//    while (q--)
//    {
//        int x1, y1, x2, y2;
//        cin >> x1 >> y1 >> x2 >> y2;
//        //x1 += 1; y1 += 1;  x2 += 1; y2 += 1;
//        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;;
//    }
//
//    return 0;
//}                                
// 
 
//#include<stack>
//int main()
//{
//    string s1 = {" 3+5 / 2 " };
//    string s;
//    for (auto e : s1)
//        if (e != ' ')s += e;
//   
//    char hao = '+';
//    stack<int>sk;
//    for (int i = 0; i < s.size(); )
//    {
//      
//        int zhi = 0;
//
//
//        while (s[i] >= '0' && s[i] <= '9')
//        {
//            zhi = zhi * 10 + (s[i] - '0');
//             i++;
//        }
//
//        if (hao == '+')
//            sk.push(zhi);
//        else if (hao == '-')
//            sk.push(-zhi);
//        else if (hao == '*')
//        {
//            int k = sk.top();
//            sk.pop();
//            sk.push(k * zhi);
//        }
//        else if (hao == '/')
//        {
//            int k = sk.top();
//            sk.pop();
//            sk.push(k / zhi);
//        }
//
//        if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')
//            hao = s[i];
//        i++;
//      
//    }
//
//    int ret = 0;
//    while (!sk.empty())
//    {
//        ret += sk.top();
//        sk.pop();
//    }
//
//    cout <<  ret << endl;
//    return 0;
//}


#include<iostream>
//#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
//int hh[10001];
//int n;  int x;  int r;  int minn = INT_MAX;  int maxx = -1;  int r1;
//int main()
//{
//    cin >> n;
//    while (n--)
//        while (cin >> x)
//        {
//            hh[x]++;
//            minn = min(minn, x);
//            maxx = max(maxx, x);
//        }
//    for (int i = minn; i <= maxx; i++)
//    {
//
//        if (hh[i] > 1) r1 = i;
//        if (hh[i] == 0) r = i;
//    }
//  
//    cout << r << " " << r1;
//    return 0;
//}


//int to_i(string s)
//{
//    int r = 0;
//    for (int i = 0; i < s.size(); i++)
//        r = r * 10 + s[i]-'0';
//
//    return r;
//}
//
//int divisorSubstrings(int num, int k) {
//    string s;  int ret = 0;  int nums = num;
//    while (nums)
//    {
//        s += nums % 10 + '0';
//        nums /= 10;
//    }
//    reverse(s.begin(), s.end());
//    int begin = 0;
//    for (int i = 0; i < s.size(); i++)
//    {
//
//        while (i - begin + 1 > k)
//        {
//            begin++;
//        }
//
//        if (i - begin + 1 == k)
//        {
//            int n = to_i(s.substr(begin, k));
//            if(n != 0)
//            if (num % n == 0) ret++;
//        }
//    }
//    return ret;
//}
//
//
//
//int main()
//{
//    int x, y;
//    cin >> x >> y;
//    cout << divisorSubstrings(x,y);
//    return 0;
//}

////#include<bits/stdc++.h>
//
//int n, x;
//vector<int> nums(1E5+1);  vector<int> dp(1E5 + 1);
////bool check(int j)
////{
////    for (int i = 1; i <= n-j; i++)
////    {
////        if (dp[i + j - 1] - dp[i - 1] < 2 * x)
////            return false;
////    }
////    return true;
////}
//
//
//bool check(int mid)
//{
//    for (int i = 1; i <= n - mid; i++)
//    {
//        //要包括0-mid区间 
//        if (dp[i + mid - 1] - dp[i - 1] < 2 * x) return false;
//    }
//    return true;
//}
//int main()
//{
//    cin >> n >> x;
//    for (int i = 1; i < n; i++)
//    {
//
//        cin >> nums[i];
//        dp[i] = nums[i] + dp[i - 1];
//    }
//    int l = 1; int r = n;
//    while (l < r)
//    {
//        int mid = l + (r - l) >> 1;
//        if (check(mid))
//            r = mid;
//        else
//            l = mid + 1;
//    }
//
//    cout << l << endl;
//    return 0;
//}


//#include<bits/stdc++.h>
//using namespace std;
//int n, x;
//vector<int> nums(1e5 + 2);
//vector<int> dp(1e5 + 3);
//bool check(int m)
//{
//    for (int i = m; i < n; i++)
//    {
//        if (dp[i] - dp[i - m] < 2 * x) return false;
//    }
//    return true;
//}
//int main()
//{
//    cin >> n >> x;
//    for (int i = 1; i < n; i++)
//    {
//        cin >> nums[i];
//        dp[i] = nums[i] + dp[i - 1];
//    }
//
//    int l = 1; int r = n;
//    while (l < r)
//    {
//        int mid = l + (r - l) / 2;
//        if (check(mid)) r = mid;
//        else l = mid + 1;
//    }
//
//    cout << l
//        return 0;
//}


//#include<bits/stdc++.h>
//using namespace std;
//long long  y;
//int main()
//{
//    y = 24;
//
//
//    cout << y* 101210121012 << endl;
//    return 0;
//}

//#include<stack>
//string decodeString(string s) {
//    stack<string> ss;  ss.push("");
//    stack<int> si;
//    for (int i = 0; i < s.size();)
//    {
//        if (s[i] >= '0' && s[i] <= '9')
//        {
//            int n = 0;
//            while (s[i] >= '0' && s[i] <= '9')
//            {
//                n = n * 10 + (s[i] - '0');
//                i++;
//            }
//            si.push(n);
//        }
//        else if (i < s.size() && s[i] >= 'a' && s[i] <= 'z')
//        {
//            string s1;  string s2 = ss.top();
//            while (i < s.size() && s[i] >= 'a' && s[i] <= 'z')
//            {
//                s1 += s[i];
//                i++;
//            }
//            ss.pop();
//            s2 += s1;
//            ss.push(s2);
//        }
//        else if (s[i] == '[')
//        {
//            i++;
//           /* if (i < s.size() && s[i] >= 'a' && s[i] <= 'z')
//            {
//                string s1;
//                while (i < s.size() && s[i] >= 'a' && s[i] <= 'z')
//                {
//                    s1 += s[i];
//                    i++;
//                }
//                ss.push(s1);
//            }*/
//        }
//        else if (s[i] == ']')
//        {
//            int n = si.top(); si.pop(); string s1 = ss.top();  ss.pop();  string s3;
//            while (n--)
//            {
//                s3 += s1;
//            }
//            string s2 = ss.top(); s2 += s3;  ss.pop();  ss.push(s2);
//            i++;
//        }
//    }
//    return ss.top();
//}
//
//int main()
//{
//    string s;
//    cin >> s;
//    cout << decodeString(s) << endl;
//    return 0;
//}
//
//
//bool dfs(vector<int>& vv, int pos, int i);
//
//int sum = 0;  int tank[4] = { 0 };  int t;  bool vis[20];
//bool makesquare(vector<int>& matchsticks) {
//    for (auto e : matchsticks)
//        sum += e;
//    if (sum % 4 != 0 || matchsticks.size() < 4) return false;
//    t = sum / 4;
//    return dfs(matchsticks, 0, 0);
//
//}
//
//bool dfs(vector<int>& vv, int pos, int i)
//{
//    if (i == 4 && pos == vv.size() ) return tank[0] == t && tank[1] == t && tank[2] == t;
//
//
//    for (int j = 0; j < vv.size(); j++)
//    {
//        if (tank[i] + vv[j] <= t && !vis[j])
//        {
//            tank[i] += vv[j];
//            vis[j] = true;
//            if (tank[i] == t)
//            {
//                if (dfs(vv, pos + 1, i + 1))return true;
//            }
//            else
//                if (dfs(vv, pos + 1, i)) return true;
//
//            vis[j] = false;
//            tank[i] -= vv[j];
//        }
//    }
//
//
//    return false;
//}
//
//int main()
//{
//    vector<int> v = { 1,1,2,2,2 };
//   cout << makesquare(v)<<endl;
//    return 0;
//}



////#include<bits/stdc++.h>
//using namespace std;
//int n; int sum = 0;  int nn = 0; int path = 1;
//void dfs(vector<int>& nums, int pos)
//{
//    if (nn == 2)
//    {
//        sum += path;
//        return;
//    }
//
//    for (int i = pos; i < n; i++)
//    {
//        nn++;
//        path *= nums[i];
//        dfs(nums, i + 1);
//        path /= nums[i];
//        nn--;
//
//    }
//}
//int main()
//{
//
//    cin >> n;
//    vector<int> nums(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> nums[i];
//    }
//    dfs(nums, 0);
//    cout << sum << endl;
//    return 0;
//}



//#include<bits/stdc++.h>
//using namespace std;
//int n;  int sum = 0;
//int main()
//{
//    cin >> n;
//    vector<int> nums(n + 1);
//    vector<int> dp(n + 1);
//    for (int i = 1; i < dp.size(); i++)
//    {
//        cin >> nums[i];
//        dp[i] = dp[i - 1] + nums[i];
//    }
//    int m = n;
//    for (int i = 1; i < dp.size(); i++)
//    {
//        sum += (dp[m] - dp[i]) * nums[i];
//    }
//    cout << sum << endl;
//
//    return 0;
//}


//#include<string>
//int main()
//{
//    int n;
//    cin >> n;
//    string s = to_string(n);
//    cout << n << endl;
//    return 0;
//}


////#include<bits/stdc++.h>
//#include<string>
////#include<bits/stdc++.h>
//using namespace std;
//bool check1(string s)
//{
//    int l = 0; int r = s.size() - 1;
//    while (l < r)
//    {
//        if (s[l++] != s[r--])
//        {
//            return false;
//        }
//    }
//    return true;
//}
//
//bool check2(string s)
//{
//    if (check1(s))
//    {
//        char a = s[0]; char b = s[1];
//        return s[2] == a && s[5] == a && s[7] == a && s[3] == b && s[4] == b && s[6] == b;
//    }
//    return false;
//}
//int main()
//{
//    int f1 = 0;  int f2 = 0;  int flag = 0;
//    int n; cin >> n;
//    int sz = n / 10000 + 1000;  int m = n % 100 + 1;
//    for (int year = n / 10000; year <= sz; year++)
//        for (int month = 1; month <= 12; month++)
//            for (int day = 1 ; day <= 31; day++)
//            {
//                if (month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12)
//                    ;
//                else if (month == 2)
//                {
//                    if ((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)
//                    {
//                        if (day > 29) break;
//                    }
//                    else
//                    {
//                        if (day > 28) break;
//                    }
//                }
//                else
//                {
//                    if (day > 30) break;
//                }
//
//                int num = year * 10000 + month * 100 + day;
//                if (num == n+1)
//                {
//                    flag = 1;
//                }
//
//                if (flag == 1)
//                {
//                    string s = to_string(num);
//
//                    if (check1(s)&&!f1)
//                    {
//                        f1++;
//                        cout << num << endl;
//                    }
//
//                    if (check2(s))
//                    {
//                        f2++;
//                        cout << num << endl;
//                    }
//                }
//               
//            }
//
//    return 0;
//}

//#include<cmath>
//int main()
//{
//    cout <<pow(9,2) << endl;
//    return 0;
//}


//#include<iostream>
//#include<string>
////#includ<bits / stdc++.h>
//using namespace std;
//
//
//bool issqrt(int num)
//{
//    if (num <= 0) return false;
//    int n = sqrt(num);
//    return n * n == num;
//}
//
//bool check(string s)
//{
//    for (int i = 1; i < s.size(); i++)
//    {
//        string s1 = s.substr(0, i); string s2 = s.substr(i, s.size() - i);
//        int num1 = stoi(s1);  int num2 = stoi(s2);
//        if (issqrt(num1) && issqrt(num2))
//            return true;
//    }
//    return false;
//}
//int main()
//{
//    int start; int en;
//    cin >> start >> en;
//    for (int i = start; i <= en; i++)
//    {
//        if (issqrt(i))
//        {
//            string s = to_string(i);
//            if (check(s)) cout << s << endl;
//        }
//    }
//    return 0;
//}
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
//int m, n;
//int dx[4] = { 0,0,1,-1 };
//int dy[4] = { 1,-1,0,0 };
//vector<int> cutline;
//int sx = 0;  int sy = 0;  int t;
//
//
//int bfs(vector<vector<int>>& nums, int i, int j)
//{
//    bool vis[55][55] = {0};
//    int ret = 0;
//    if (nums[i][j] == t) return ret;
//    queue<pair<int, int>>q;
//    q.push({ i,j });  vis[i][j] = true;
//while (!q.empty())
//    {
//        int sz = q.size(); ret++;
//        while (sz--)
//        {
//            auto [a, b] = q.front(); q.pop();
//            for (int i = 0; i < 4; i++)
//            {
//                int x = dx[i] + a; int y = dy[i] + b;
//                if (x >= 0 && x < m && y >= 0 && y < n && nums[x][y] != 0&&!vis[x][y])
//                {
//                    if (nums[x][y] == t)
//                    {
//                        sx = x;
//                        sy = y;
//                        return ret;
//                    }
//                    q.push({ x,y }); vis[x][y] = true;
//                }
//            }
//        }
//    }
//
//    return -1;
//}
//
//
//int cutOffTree(vector<vector<int>>& forest) {
//    int ret = 0;
//    m = forest.size();  n = forest[0].size();
//    for (auto e : forest)
//    {
//        for (auto h : e)
//        {
//            if (h > 1) cutline.push_back(h);
//        }
//    }
//    sort(cutline.begin(), cutline.end());
//
//    for (auto e : cutline)
//    {
//        t = e;
//        int jie = bfs(forest, sx, sy);
//        if (jie == -1)
//            return -1;
//        else
//            ret += jie;
//    }
//
//
//
//    return ret;
//}
//
//int main()
//{
//    int t = 5;
//    vector<vector<int>> vv = {{2,3,4 },{0, 0, 5},{8, 7, 5}};
//    cout << cutOffTree(vv) << endl;
//    return 0;
//}


//#include<bits/stdc++.h>
//#include<string>
//using namespace std;
//char wei[36] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
//string suan(int n, int i, int j)
//{
//    string sum; int tmp = 0; int num = i * j;  int ret;
//    while (num)
//    {
//        sum += wei[num%n];
//        num /= n;
//    }
//    reverse(sum.begin(), sum.end());
//    return sum;
//}
//int main()
//{
//    int n;
//    cin >> n;
//    for (int i = 1; i < n; i++)
//    {
//        for (int j = 1; j <= i; j++)
//        {
//            cout << i << '*' << j << '=' << suan(n, i, j) << " ";
//        }
//        cout << endl;
//    }
//    return 0;
//}

#include<string>
#include<stack>
//int calculate(string s) {
//    stack<int> sk;  sk.push(0);
//    int hao = 1; sk.push(hao);
//    for (int i = 0; i < s.size();)
//    {
//        if (s[i] >= '0' && s[i] <= '9')
//        {
//            string s1;
//            while (i < s.size() && s[i] >= '0' && s[i] <= '9')
//                s1 += s[i++];
//            int num = sk.top();  sk.pop();
//            num *= stoi(s1);  sk.top() += num * hao;
//        }
//        else if (s[i] == '+')
//        {
//            sk.push(1);
//            i++;
//        }
//        else if (s[i] == '-')
//        {
//            sk.push(-1);
//            i++;
//        }
//        else if (s[i] == '(')
//        {
//            sk.push(0);
//            sk.push(1); i++;
//            if (s[i ] == ' '|| s[i ] == '-')
//            {
//                sk.pop();
//                while (s[i] == ' ') i++;
//                if (s[i] == '-')
//                {
//                    sk.push(-1); i++;
//                }
//                else sk.push(1);
//            }
//
//        }
//        else if (s[i] == ')')
//        {
//            int num = sk.top();  sk.pop();
//            num *= sk.top(); sk.pop();  sk.top() += num;
//            i++;
//        }
//        else
//            i++;
//    }
//
//    return sk.top();
//}
//
//
//int main()
//{
//    string s = "12-(-22)";
//    
//    cout << calculate(s);
//    return 0;
//}




//int m, n;
//int dx[4] = { 1,-1,0,0 };
//int dy[4] = { 0,0,1,-1 };
//vector<vector<bool>> vis;
//int numEnclaves(vector<vector<int>>& grid) {
//    int ret = 0;
//    queue<pair<int, int>> q;  m = grid.size();  n = grid[0].size();
//    vis = vector<vector<bool>>(m, vector<bool>(n, false));
//    for (int i = 0; i < m; i++)
//    {
//        if (grid[i][0] == 1 && !vis[i][0])
//        {
//            q.push({ i,0 }); vis[i][0] = true;
//        }
//
//        if (grid[i][n - 1] == 1 && !vis[i][n - 1])
//        {
//            q.push({ i,n - 1 }); vis[i][n - 1] = true;
//        }
//    }
//
//    for (int i = 1; i < n - 1; i++)
//    {
//        if (grid[0][i] == 1 && !vis[0][i])
//        {
//            q.push({ 0,i }); vis[0][i] = true;
//        }
//
//        if (grid[m - 1][i] == 1 &&! vis[m - 1][i])
//        {
//            q.push({ m - 1,i }); vis[m - 1][i] = true;
//        }
//    }
//
//    while (!q.empty())
//    {
//        int sz = q.size();
//        while (sz--)
//        {
//            auto [a, b] = q.front(); q.pop();
//            for (int i = 0; i < 4; i++)
//            {
//                int x = dx[i] + a; int y = dy[i] + b;
//                if (x >= 0 && x < m && y >= 0 && y < 0 && !vis[x][y] && grid[x][y] == 1)
//                {
//                    vis[x][y] = true;
//                    q.push({ x,y });
//                }
//            }
//        }
//    }
//
//    for (int i = 1; i < m - 1; i++)
//    {
//        for (int j = 1; j < n - 1; j++)
//        {
//            if (grid[i][j] == 1 && !vis[i][j])
//            {
//                ret++;
//            }
//        }
//    }
//    return ret;
//}
//
//
//int main()
//{
//    vector<vector<int>> vv = { {0,1,1,0},{0,0,1,0},{0,0,1,0},{0,0,0,0} };
//   cout <<  numEnclaves(vv) << endl;
//    return 0;
//}



//#include<bits/stdc++.h>

//#include<bits/stdc++.h>
//using namespace std;
//
//int main()
//{
//    long long a, b, n;
//    cin >> a >> b >> n;
//    long long nums[7] = { b,a,a,a,a,a,b };
//
//    long long x1, x2, n1;  n1 = 5 * a + 2 * b;
//    x1 = n / n1;   x2 = n % n1;
//    long long i = 0, j = 0;
//    while (j < x2)
//    {
//        j += nums[i % 7];
//        i++;
//    }
//    cout << x1 * 7 + i << endl;
//    return 0;
//}
#include<unordered_set>
//string alienOrder(vector<string>& words) {
//    unordered_map<int, vector<int>> hh;  string s;
//    unordered_map<int, int> in;
//    unordered_map<int,int> h1;
//    for (int i = 1; i < words.size(); i++)
//    {
//        for (int j = 0; j < min(words[i - 1].size(), words[i].size()); j++)
//        {
//            if (words[i - 1][j] != words[i][j])
//            {
//                h1[words[i - 1][j] - 'a']++;
//                h1[words[i][j] - 'a']++;
//                hh[words[i - 1][j]-'a'].push_back(words[i][j]-'a');
//                in[words[i][j]-'a']++;
//                break;
//            }
//        }
//    }
//
//    queue<int> q;
//    for (const auto& e : h1)
//    {
//        if (in[e.first] == 0)
//        {
//            q.push(e.first);  s += (e.first + 'a');
//        }
//    }
//
//    while (!q.empty())
//    {
//        int sz = q.size();
//        while (sz--)
//        {
//            int n = q.front(); q.pop();
//            for (auto e : hh[n])
//            {
//                in[e]--;
//                if (in[e] == 0)
//                {
//                    q.push(e);
//                    s += (e+'a');
//                }
//            }
//        }
//    }
//    return s;
//}
//
//
//int main()
//{
//    vector<string> words = { "wrt","wrf","er","ett","rftt"};
//  cout <<  alienOrder(words) << endl;
//    return 0; 
//}


//vector<int> subSort(vector<int>& array) {
//    vector<int> ans = { -1,-1 };
//    if (array.size() == 0) { return ans; }
//    int max = array[0], min = array[array.size() - 1];
//    for (int right = 0, left = array.size() - 1; right < array.size(); right++, left--) {
//        if (array[right] < max) { ans[1] = right; }
//        else { max = array[right]; }
//        if (array[left] > min) { ans[0] = left; }
//        else { min = array[left]; }
//    }
//    return ans;
//}
//
//int main()
//{
//    vector<int> nun = { 1,2,4,7,10,11,7,12,6,7,16,18,19 };
//   nun = subSort(nun);
//   for (auto e : nun)
//       cout << e << " ";
//    return 0;
//}


//#include<iostream>
//#include<vector>
//using namespace std;
//
//vector<long long>t, d, l;  long long now = 0; vector<bool>vis;
//bool dfs(long long pos)
//{
//    if (pos == t.size())
//        return true;
//    for (long long i = 0; i < t.size(); i++)
//    {
//        if (!vis[i] && (t[i] + d[i]) >= now)
//        {
//            vis[i] = true;
//            now += l[i];
//            if (dfs(pos + 1))return true;
//            now -= l[i];
//            vis[i] = false;
//        }
//    }
//    return false;
//}
//int main()
//{
//    long long n, s;
//    cin >> n;
//    while (n--)
//    {
//        cin >> s;
//        t = d = l = vector<long long>(s); vis = vector<bool>(s, false);
//        for (long long i = 0; i < s; i++)
//            cin >> t[i] >> d[i] >> l[i];
//        if (dfs(0)) cout << "YES" << endl;
//        else cout << "NO" << endl;
//    }
//    return 0;
//}


//#include<bits/stdc++.h>
//using namespace std;
//bool check(string s)
//{
//    int t = 1;
//    for (int i = s.size() - 1; i >= 0; i--)
//    {
//        if (t % 2 == 1)
//        {
//            if ((s[i] - '0') % 2 == 0) return false;
//        }
//        else
//        {
//            if ((s[i] - '0') % 2 == 1)return false;
//        }
//        t++;
//    }
//
//    return true;
//}
//int main()
//{
//    int n;
//    cin >> n; int ret = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        string s = to_string(i);
//        if (check(s)) ret++;
//    }
//    cout << ret << endl;
//    return 0;
//}


//#include<unordered_map>
////#include<bits/stdc++.h>
//using namespace std;
//int n, q;
//vector<vector<int>> tu;
//vector<int> food;
//int ret = 0;
//vector<vector<int>> line;
//vector<int>path;
//void dfs(int start,int endd)
//{
//    if (start == endd)
//    {
//        line.push_back(path);
//        return;
//    }
//    if (path.size() > n) return;
//    for (int i  =1 ; i <= n;i++)
//    {
//        if (tu[start][i] == 1)
//        {
//            path.push_back(i);
//            dfs(i,endd);
//            path.pop_back();
//        }
//    }
//}
//int main()
//{
//
//    cin >> n >> q;
//    food = vector<int>(n+1);
//    tu = vector<vector<int>>(n + 1, food);
//    for (int i = 1; i <= n; i++)
//    {
//        int x;
//        cin >> x;
//        food[i] = x;
//    }
//    for (int i = 1; i < n; i++)
//    {
//        int x, y;
//        cin >> x >> y;
//        tu[x][y] = 1;
//        tu[y][x] = 1;
//    }
//
//    while (q--)
//    {
//        int start, endd;
//        cin >> start >> endd;
//        ret = 0;
//        dfs(start,endd);
//        int minn = INT_MAX; int f = 0;
//        for (int i = 0; i < line.size(); i++)
//        {
//            if (line[i].size() < minn)
//            {
//                f = i;
//                minn = line[i].size();
//            }
//        }
//        unordered_set<int>s;
//        for (auto e : line[f])
//            s.insert(food[e]);
//
//
//        cout <<s.size()<< endl;
//    }
//
//    return 0;
//}



//#include<bits/stdc++.h>

//#include<bits/stdc++.h>
//using namespace std;
//typedef long long LL;
//const int maxn = 1e6 + 5; 
//const int inf = 0x3f3f3f3f; 
//int n, f[maxn], fd, lenf; 
//char s[maxn]; 
//
//void add()
//{
//    int flag = 0; 
//    for (int i = 0; i < lenf; i++) 
//    {
//        f[i] = f[i] + f[i] + flag; 
//        flag = (f[i] >= 10); 
//        f[i] %= 10; 
//    }
//    if (flag) f[lenf++] = flag; 
//}
//
//int main()
//{
//    scanf("%d %s", &n, s); 
//    int len = strlen(s); 
//    for (int i = len - 1; i >= 0; i--) 
//        if (s[i] != '.') 
//            f[lenf++] = s[i] - '0'; 
//        else
//            fd = len - 1 - i; 
//    while (n--)
//        add(); 
//    if (f[fd - 1] >= 5) 
//    {
//        int flag = 1;
//        for (int i = fd; i < lenf; i++) 
//        {
//            f[i] = f[i] + flag; 
//            flag = (f[i] >= 10); 
//            f[i] %= 10; 
//        }
//        if (flag) f[lenf++] = flag; 
//    }
//    for (int i = lenf - 1; i >= fd; i--)
//        cout << f[i];
//    cout << endl;
//    return 0;
//
//}


//int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
//    int m = obstacleGrid.size();  int n = obstacleGrid[0].size();
//    vector<vector<int>> vv;
//    vv = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));  vv[1][1] = 1;
//    for (int i = 1; i <= m; i++)
//    {
//        for (int j = 1; j <= n; j++)
//        {
//            if (obstacleGrid[i - 1][j - 2] != 1) vv[i][j] += vv[i][j - 1];
//
//            if (obstacleGrid[i - 2][j - 1] != 1) vv[i][j] += vv[i - 1][j];
//        }
//    }
//
//    return vv[m][n];
//}
//
//int main()
//{
//    vector<vector<int>> num = { {0,0,0 }, { 0,1,0 }, { 0,0,0 }
//};
//    cout << uniquePathsWithObstacles(num) << endl;
//    return 0;
//}




//1.2 像剥洋葱一样解决最小高度树
//unordered_map<int, vector<int>> hh;
//vector<int> ret;
//vector<int> du;
//vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
//    vector<bool> vis(n, false);
//    if (n == 1) return { 0 };
//    du = vector<int>(n, 0);
//    for (auto e : edges)
//    {
//        int a = e[0]; int b = e[1];
//        du[a]++; du[b]++;
//        hh[a].push_back(b);
//        hh[b].push_back(a);
//    }
//
//    queue<int> q;
//
//
//    for (int i = 0; i < du.size(); i++)
//        if (du[i] == 1)
//        {
//            q.push(i);
//            vis[i] = true;
//
//        }
//
//    while (!q.empty())
//    {
//
//        if (n == 1) ret.push_back(q.front());
//
//        if( n == 2&& du[q.front()] == du[q.back()]) return {q.front(),q.back()};
//        int sz = q.size();
//        n -= sz;
//
//        while (sz--)
//        {
//            int num = q.front(); q.pop();
//            for (auto e : hh[num])
//            {
//                du[e]--;
//                if (!vis[e] && du[e] == 1)
//                {
//                    q.push(e);
//                    vis[e] = true;
//                }
//                
//            }
//        }
//    }
//    return ret;
//}
//
//
//int main()
//{
//    vector<vector<int>> hh = { {3,0 }, { 3,1 }, { 3,2 }, { 3,4 }, { 5,4 } };
//    findMinHeightTrees(6, hh);
//    return 0;
//}
//   


//int minFallingPathSum(vector<vector<int>>& matrix) {
//    int n = matrix.size();
//    int m = matrix[0].size();
//    for (int i = 1; i < n; i++)
//    {
//        for (int j = 0; j < m; j++)
//        {
//            int a = INT_MAX; int b = matrix[i - 1][j];  int c = a;
//            if (j > 0) matrix[i - 1][j - 1];
//            if (j < m - 1) matrix[i - 1][j + 1];
//
//            a = min(a, b);  a = min(a, c);
//            matrix[i][j] += a;
//        }
//    }
//
//    sort(matrix[n - 1].begin(), matrix[n - 1].end());
//    return matrix[n - 1][0];
//
//}
//
//int main()
//{
//    vector<vector<int>>vv = { {2,1,3},{6,5,4},{7,8,9} };
//    minFallingPathSum(vv);
//    return 0;
//}


//
//int rob(vector<int>& nums) {
//    int n = nums.size();
//    if (n == 0) return 0;
//   // if (n == 1) return nums[0];
//    vector<int> f(n);
//    vector<int> g(n);
//
//    for (int i = 2; i < n - 1; i++)
//    {
//        f[i] = nums[i] + g[i - 1];
//
//        g[i] = max(g[i - 1], f[i - 1]);
//    }
//    int  x = max(f[n - 2], g[n - 2]) + nums[0];
//
//    f[0] = 0;
//    g[0] = 0;
//    for (int i = 1; i < n; i++)
//    {
//        f[i] = nums[i] + g[i - 1];
//
//        g[i] = max(g[i - 1], f[i - 1]);
//    }
//    int y = max(f[n - 1], g[n - 1]);
//
//    return max(x, y);
//}
//
//int main()
//{
//    vector<int> r = {1};
//    rob(r);
//    return 0;
//}


//int deleteAndEarn(vector<int>& nums) {
//    vector<int> num;  sort(nums.begin(), nums.end());
//    int hh[10001] = { 0 };   int prev = -1;
//    for (int i = 0; i < nums.size(); i++)
//    {
//        hh[nums[i]]++;
//        if (nums[i] != prev)
//        {
//            prev = nums[i];
//            num.push_back(nums[i]);
//        }
//    }
//    int n = num.size();
// 
//
//    vector<int> f(n);
//    vector<int> g(n);
//
//    f[0] = hh[num[0]] * num[0];
//    for (int i = 1; i < n; i++)
//    {
//        if (num[i] - num[i - 1] == 1)
//            f[i] = hh[num[i]] * num[i] + g[i - 1];
//        else f[i] = hh[num[i]] * num[i] + max(f[i - 1], g[i - 1]);
//
//        g[i] = max(f[i - 1], g[i - 1]);
//    }
//
//    return max(f[n - 1], g[n - 1]);
//}
//
//
//int main()
//{
//    vector<int> num = { 8,10,4,9,1,3,5,9,4,10 };
//    deleteAndEarn(num);
//    return 0;
//}



//vector<int> ret;
//vector<int> rightSideView(TreeNode* root) { //高度 一层一层 用队列
//    if (root == nullptr) return ret;
//    queue<TreeNode*> q; q.push(root); ret.push_back(root->val);
//    while (!q.empty())
//    {
//        int sz = q.size();  int f = 1;
//        while (sz--)
//        {
//            TreeNode* cur = q.front(); q.pop();
//            if (cur->right)
//            {
//                q.push(cur->right);
//                if (f)
//                {
//                    ret.push_back(cur->right->val);
//                    f = 0;
//                }
//            }
//
//            if (cur->left)
//            {
//                q.push(cur->left);
//                if(f)
//                {
//                    ret.push_back(cur->left->val);
//                    f = 0;
//                }
//
//            }
//
//        }
//    }
//
//
//
//
//    return ret;
//}


//int deleteAndEarn(vector<int>& nums) {
//    const int N = 10001;
//    int arr[N] = { 0 };
//    for (auto e : nums) arr[e] += e;
//    vector<int> f(N);
//    auto g = f;
//    for (int i = 1; i < N; i++)
//    {
//        f[i] = g[i - 1] + arr[i];
//        g[i] = max(g[i - 1], f[i - 1]);
//    }
//
//    return max(g[N - 1], f[N - 1]);
//}



//bool check(int l, int r, string s1);
//
//unordered_map<char, long long> hh1;
//long long validSubstringCount(string word1, string word2) {//二象性 二分 哈希  
//
//    long long ret = 0;
//    for (auto e : word2)
//        hh1[e]++;
//    int n = word1.size();
//    for (int i = 0; i <= n - word2.size(); i++)
//    {
//        int l = i;  int r = n - 1;
//        int mid;
//        while (l < r)
//        {
//            mid = l + (r - l) / 2;
//            if (check(i, mid, word1))
//                r = mid;
//            else l = mid + 1;
//        }
//        ret += (r - mid + 1);
//    }
//
//    return ret;
//}
//bool check(int l, int r, string s1)
//{
//    unordered_map<char, long long> hh2 = hh1;
//    for (int i = l; i <= r; i++)
//    {
//        hh2[s1[i]]--;
//    }
//    for (auto e : hh2)
//        if (e.second > 0) return false;
//    return true;
//}
//
//int main()
//{
//    string s1, s2;
//    s1 = "bcca";
//    s2 = "abc";
//    validSubstringCount(s1 , s2);
//    return 0;
//}


//int maxProfit(vector<int>& prices) {
//    int n = prices.size();
//    vector<vector<int>>buy(n, vector<int>(3, -0x3f3f3f3f));
//    auto sale = buy;
//    buy[0][0] = -prices[0];
//    sale[0][0] = 0;
//    for (int i = 1; i < n; i++)
//    {
//        for (int j = 0; j < 3; j++)
//        {
//            buy[i][j] = max(buy[i - 1][j], (sale[i - 1][j] - prices[i]));
//            sale[i][j] = sale[i - 1][j];
//            if (j - 1 >= 0)
//                sale[i][j] = max(sale[i][j], (buy[i - 1][j - 1] + prices[i]));
//
//        }
//    }
//
//    return max(sale[n - 1][0], max(sale[n - 1][1], sale[n - 1][2]));
//}



//int maxSubarraySumCircular(vector<int>& nums) {
//    int n = nums.size();
//    vector<int> f(n);
//    auto g = f;
//    f[0] = g[0] = nums[0];
//    int sum = nums[0];
//    int maxx, minn;  maxx = minn = sum;
//    for (int i = 1; i < n; i++)
//    {
//        sum += nums[i];
//        f[i] = max(nums[i], f[i - 1] + nums[i]);
//
//        g[i] = min(nums[i], g[i - 1] + nums[i]);
//        maxx = max(maxx, f[i]);
//        minn = min(minn, g[i]);
//    }
//    if (sum - minn == 0)
//        return maxx;
//    else
//        return max(sum - minn, maxx);
//}


//int maxProduct(vector<int>& nums) {
//    int n = nums.size();
//    vector<int> f(n);
//    auto g = f;
//    g[0] = f[0] = nums[0];
//    int maxx = nums[0];
//    for (int i = 1; i < n; i++)
//    {
//        g[i] = min(nums[i], min(g[i - 1] * nums[i], f[i - 1] * nums[i]));
//        f[i] = max(nums[i], max(f[i - 1] * nums[i], g[i - 1] * nums[i]));
//        maxx = max(maxx, f[i]);
//    }
//
//    return maxx;
//}


//int maxTurbulenceSize(vector<int>& arr) {
//    int n = arr.size();
//    vector<int> dp(n);
//    dp[0] = 1;
//    int maxx = 1;
//    for (int i = 1; i < n; i++)
//    {
//        if (arr[i] == arr[i - 1])
//        {
//            dp[i] = 1;
//        }
//        else
//        {
//            dp[i] = 2;
//            if (i >= 2 && dp[i] > dp[i - 1] && dp[i - 1] < dp[i - 2])
//                dp[i] = dp[i - 1] + 1;
//            else if (i >= 2 && dp[i] < dp[i - 1] && dp[i - 1] > dp[i - 2])
//                dp[i] = dp[i - 1] + 1;
//        }
//        maxx = max(maxx, dp[i]);
//    }
//    return maxx;
//}
//
//
//int main()
//{
//    vector<int>arr = { 9,4,2,10,7,8,8,1,9 };
//    maxTurbulenceSize(arr);
//    return 0;
//}



//int findSubstringInWraproundString(string s) {
//
//    int n = s.size();
//    int hh[26] = { 0 };
//    vector<int> dp(n, 1);
//
//    for (int i = 1; i < n; i++)
//    {
//        if ((s[i - 1] == 'z' && s[i] == 'a') || (s[i] - s[i - 1] == 1))
//            dp[i] += dp[i - 1];
//
//    }
//
//    int ret = 0;
//    for (int i = 0; i < n; i++)
//        hh[s[i] - 'a'] = max(hh[s[i] - 'a'], dp[i]);
//
//
//    for (auto e : hh)
//        ret += e;
//    return ret;
//}


//int main()
//{
//    vector<int> nums = {7,2,7,9,8,1,1,2,9,0,6,9,1};
//    int maxval = nums[0]; int count = 1;
//    for (int i = 0 ; i < nums.size(); i++)
//    {
//        if (maxval == nums[i]) count++;
//        else if (maxval < nums[i])
//        {
//            maxval = nums[i];
//            count = 1;
//        }
//    }
//
//    cout << maxval << " " << count << endl;
//    return 0;
//}



//int findNumberOfLIS(vector<int>& nums) {
//    int n = nums.size();
//    vector<int> dp(n, 1);
//    auto ap = dp;
//    int maxx = 1;
//    for (int i = 1; i < n; i++)
//    {
//        for (int j = 0; j < i; j++)
//        {
//            if (nums[i] > nums[j])
//            {
//                if (dp[j] + 1 == dp[i])
//                    ap[i] += ap[j];
//                else if (dp[j] + 1 > dp[i])
//                {
//                    dp[i] = dp[j] + 1;
//                    ap[i] = ap[j];
//                }
//            }
//        }
//        maxx = max(maxx, dp[i]);
//    }
//    int ret = 0;
//    for (int i = 0; i < n; i++)
//    {
//        if (maxx == dp[i]) ret += ap[i];
//    }
//    return ret;
//}



//#include<iostream>
//#include<cstdio>
//using namespace std;
//int main()
//{
//    int a, b;
//    cin >> a >> b;
//    
//    printf("%.3lf%%", b*100.0 / a);
//    return 0;
//}


//#include<iostream>
//#include<vector>
//using namespace std;
//int main()
//{
//    int n; cin >> n;
//    vector<int>v(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v[i];
//    }
//    for (int i = 0; i < n - 1; i++)
//    {
//
//        for (int j = 1; j < n - i; j++)
//        {
//            if (v[j - 1] > v[j])
//            {
//                int tmp = v[j - 1];
//                v[j - 1] = v[j];
//                v[j] = tmp;
//            }
//
//        }
//    }
//
//    for (auto e : v)
//        cout << e << endl;
//
//    return 0;
//}


//#include<iostream>
//#include<vector>
//using namespace std;
//int main()
//{
//    int m, n;
//    cin >> m >> n;
//    vector<vector<int>>vv(m, vector<int>(n));
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            cin >> vv[i][j];
//        }
//    }
//
//    for (int i = 0; i < m ; i++)
//    {
//        for (int j = 0; j < n ; j++)
//        {
//            if (i == 0 || i == m - 1 || j == 0 || j == n - 1)
//                cout << vv[i][j] << " ";
//            else
//            {
//                float x = (vv[i][j] + vv[i - 1][j] + vv[i][j - 1] + vv[i + 1][j] + vv[i][j + 1]) / 5.0;
//                cout << (int)(x + 0.5) << " ";
//            }
//        }
//        cout << endl;
//    }
//   
//    return 0;
//}

//#include<iostream>
//#include<string>
//using namespace std;
//int main()
//{
//    int n;
//    cin >> n;
//    cin.ignore();
//    while (n--)
//    {
//        string s;  getline(cin, s);
//        int n = s.size();
//        for (int i = 1; i < n; i++)
//            if (s[i] >= 'A' && s[i] <= 'Z') s[i] += 32;
//
//        if (s[0] >= 'a' && s[0] <= 'z') s[0] -= 32;
//        cout << s << endl;
//    }
//    return 0;
//}

//
//#include<iostream>
//#include<string>
//using namespace std;
//int main()
//{
//    string s; getline(cin, s);
//    int d = s.size();
//    for (int i = 0; i < d - 1; i++)
//    {
//        cout << (char)(s[i] + s[i + 1]);
//    }
//    cout << (char)(s[0] + s[d - 1]);
//    return 0;
//}


//#include<iostream>
//#include<string>
//using namespace std;
//int hh[128];
//int main()
//{
//    char s1[1100];
//    cin >> s1; int i = 0;
//    while (s1[i])
//    {
//        hh[s1[i]]++;
//        i++;
//    }
//    i = 0;
//    while (s1[i])
//        if (hh[s1[i++]] == 1)
//        {
//            cout << s1[i] << endl;
//            return 0;
//        }
//
//    cout << "no" << endl;
//    return 0;
//}


//#include<iostream>
//#include<string> // Rock Scissors Paper
//using namespace std;
//int main()
//{
//    int n;
//    string s1, s2;
//    cin >> n;
//    while (n--)
//    {
//        cin >> s1 >> s2;
//        if (s1 == s2)
//            cout << "Tie" << endl;
//         if ((s1 == "Rock" && s2 == "Scissors") || (s1 == "Scissors" && s2 == "Paper") || (s1 == "Paper" && s2 == " Rock"))
//            cout << "Player1" << endl;
//         if ((s2 == "Rock" && s1 == "Scissors") || (s2 == "Scissors" && s1 == "Paper") || (s2 == "Paper" && s1 == " Rock"))
//            cout << "Player2" << endl;
//
//    }
//    return 0;
//}


//#include<iostream>
//#include<string>
//using namespace std;
//int main()
//{
//    int n; cin >> n;
//    string s;
//    cin >> s;
//    int x;
//    while (n--)
//    {
//        cin >> x;
//        if (x == 1)
//        {
//            string s1; cin >> s1;
//            s += s1; cout << s << endl;
//        }
//        else if (x == 2)
//        {
//            int a, b;
//            cin >> a >> b;
//            s = s.substr(a, b);
//            cout << s << endl;
//        }
//        else if (x == 3)
//        {
//            int a; string s1;
//            cin >> a >> s1;
//            s.insert(a, s1);  cout << s << endl;
//        }
//        else if(x == 4)
//        {
//            string s1;
//            cin >> s1;
//            size_t pos = s.find(s1);
//            if (pos != string::npos) cout << pos << endl;  //这里的条件判断需要记忆
//            else cout << -1 << endl;
//        }
//    }
//    return 0;
//}

//#include<iostream>
//#include<string>
//using namespace std;
//int main()
//{
//    string s;
//    getline(cin, s);
//    int ret = 0;
//    for (auto e : s)
//    {
//        if (e == ' ')
//        {
//            if (ret == 0)
//                continue;
//            cout << ret << ',';
//            ret = 0;
//        }
//        else ret++;
//    }
//    cout << ret;
//    return 0;
//}

//#include<iostream>
//#include<string>
//#include<algorithm>
//using namespace std;
//int main()
//{
//    string s;
//    while (cin >> s)  //这里还有一些有关循环输入疑问
//    {
//        reverse(s.begin(), s.end());
//        cout << s << endl;
//
//    }
//    return 0;
//}


//#include<iostream>
//#include<string>
//using namespace std;
//int main()
//{
//    int n; string s; char x;
//    cin >> n;
//    while (n--)
//    {
//        cin >> s;  string a, b;
//        if (s[0] >= 'a' && s[0] <= 'c')
//        {
//            x = s[0];
//            cin >> a >> b;
//        }
//        else
//        {
//            a = s; cin >> b;
//        }
//        
//        if (x == 'a')
//        {
//            string c = to_string(stoi(a) + stoi(b));
//            cout << a << '+' << b << '=' << c << endl;
//            cout << a.size() + b.size() + c.size() + 2 << endl;
//
//        }
//        else if (x == 'b')
//        {
//            string c = to_string(stoi(a) - stoi(b));
//            cout << a << '-' << b << '=' << c << endl;
//            cout << a.size() + b.size() + c.size() + 2 << endl;
//
//        }
//        else if (x == 'c')
//        {
//            string c = to_string(stoi(a) * stoi(b));
//            cout << a << '*' << b << '=' << c << endl;
//            cout << a.size() + b.size() + c.size() + 2 << endl;
//
//        }
//        
//
//
//    }
//    return 0;
//}


//#include<iostream>
//#include<string>
//using namespace std;
//int main()
//{
//    string s, t;
//    cin >> s >> t;
//    int n, a, b, c, d;
//    cin >> n;
//    while (n--)
//    {
//        cin >> a >> b >> c >> d;
//        string s1, t1;
//        a--; b--; c--; d--;
//        s1 = s.substr(a, b-a+1);
//        t1 = t.substr(c, d-c+1);
//        if (s1 > t1)
//            cout << "erfusuer" << endl;
//        else if (s1 < t1)
//            cout << "yifusuyi" << endl;
//        else cout << "ovo" << endl;
//    }
//    return 0;
//}

//#include<iostream>
//#include<vector>
//using namespace std;
//int main()
//{
//    int n;
//    while (cin >> n)
//    {
//        vector<int>v;
//        for (int i = 0; i < n; i++)
//        {
//            cin >> v[i];
//        }
//        int m; cin >> m; int f = 0;
//        for (int i = 0; i < n; i++)
//            if (m == v[i])
//            {
//                cout << i << endl;
//                f = 1;
//                break;
//            }
//        if (!f) cout << "No" << endl;
//    }
//    return 0;
//}

//#include<iostream>
//#include<vector>
//#include<cstdio>
//#include<algorithm>
//using namespace std;
//int main()
//{
//    int m, n;
//    scanf_s("%d %d", &m, &n);
//    vector<int>v(m);
//    for (int i = 0; i < m; i++)
//    {
//        scanf_s("%d", &v[i]);
//    }
//    sort(v.begin(), v.end());
//    printf("%d\n", v[n]);
//    return 0;
//}


//#include <iostream>
//using namespace std;
//int calc(int x, char c, int y)
//{
//    switch (c)
//    {
//    case '+':
//        return x + y;
//    case '-':
//        return x - y;
//    case '*':
//        return x * y;
//    case '/':
//        return x / y;
//    case '%':
//        return x % y;
//    }
//}
//int main()
//{
//    int a = 0, b = 0;
//    char c = 0;
//    //cin 会?动跳过空格 
//    cin >> a >> c >> b;
//    int ret = calc(a, c, b);
//    cout << ret << endl;
//    return 0;
//}


//#include<iostream>
//#include<string>
//#include<cmath>
//using namespace std;
//bool check(int x)
//{
//    for (int i = 2; i <= sqrt(x); i++)
//    {
//        if (x % i == 0)
//            return false;
//    }
//    return true;
//}
//bool cccc(string s)
//{
//    int l = 0; int r = s.size() - 1;
//    while (l < r)
//    {
//        if (s[l] != s[r]) return false;
//        l++; r--;
//    }
//    return true;
//}
//int main()
//{
//    int n; cin >> n; int r = 0;
//    for (int i = 11; i <= n; i++)
//    {
//        if (check(i))
//        {
//            string s; s = to_string(i);
//            if (cccc(s)) r++;
//        }
//    }
//    cout << r << endl;
//    return 0;
//}


//#include<iostream>
//#include<cmath>
//using namespace std;
//bool check(int x)
//{
//    for (int i = 2; i <= sqrt(x); i++)
//    {
//        if (x % i == 0)
//            return false;
//    }
//    return true;
//}
//int dao(int x)
//{
//    int y = 0;
//    while (x)
//    {
//        y = y * 10 + x % 10;
//        x /= 10;
//    }
//    return y;
//}
//int main()
//{
//    int m, n;
//    cin >> m >> n;
//    for (int i = m; i <= n; i++)
//    {
//        if (check(i) && check(dao(i)))
//        {
//            cout << i << ",";
//        }
//    }
//    return 0;
//}


//#include<iostream>
//#include<string>
//using namespace std;
//string s = "0123456789ABCDEF";
//string jinzhi(int n, int m)
//{
//    if (n == 0)
//    {
//        string r;
//        return r;
//    }
//        
//
//    return jinzhi(n / m, m) + s[n % m];
//}
//int main()
//{
//    int n, m;
//    cin >> n >> m;
//    cout << jinzhi(n, m) << endl;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//int main()
//{
//    int a, b;
//    cin >> a >> b;
//    a = a ^ b;
//    b = a ^ b;
//    a = a ^ b;
//
//    cout << a << " " << b << endl;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//struct student
//{
//    int q, w, e;
//    student(int a = 0, int b = 0, int c = 0)
//    {
//        this->q = a; this->w = b; this->e = c;
//    }
//
//    void show()
//    {
//        int z = this->w * 7 + this->e * 3;
//        if (this->w + this->e > 140 && z > 800)
//            cout << "Excellent" << endl;
//        else
//            cout << "Not excellent" << endl;
//    }
//
//};
//
//int main()
//{
//    int n;
//    cin >> n;
//    int a, b, c;
//    while (n--)
//    {
//        cin >> a >> b >> c;
//        student x(a, b, c);
//        x.show();
//    }
//    return 0;
//}


//#include<iostream>
//#include<algorithm>
//#include<vector>
//#include<string>
//using namespace std;
//struct man
//{
//    string name;  int year; int month; int day; int id;
//    man(string n = "", int y = 0, int m = 0, int d = 0, int i = 0)
//    {
//        this->name = n;  this->year = y;  this->month = m; this->day = d;
//        this->id = i;
//    }
//};
//bool cmp(man m1, man m2)
//{
//    if (m1.year != m2.year)
//        return m1.year < m2.year;
//    else if (m1.month != m2.month)
//        return m1.month < m2.month;
//    else if (m1.day != m2.day)
//        return m1.day < m2.day;
//    else
//        return m1.id > m2.id;
//
//}
//int main()
//{
//    int n; cin >> n;  vector<man> v(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v[i].name >> v[i].year >> v[i].month >> v[i].day;
//        v[i].id = i;
//    }
//    sort(v.begin(), v.end(), cmp);
//    for (auto e : v)
//        cout << e.name << endl;
//    return 0;
//}


//#include<iostream>
//#include<vector>
//using namespace std;
//int main()
//{
//    int n, p;
//    cin >> n >> p;
//    vector<vector<int>> vv(n + 1);  int x;
//    while (p--)
//    {
//        cin >> x;
//        if (x == 1)
//        {
//            int i, j, k; cin >> i >> j >> k;
//            if (vv[i].size() < j + 1) vv[i].resize(j + 10);
//            vv[i][j] = k;
//        }
//        else if (x == 2)
//        {
//            int i, j; cin >> i >> j;
//            if (vv[i][j])
//                cout << vv[i][j] << endl;
//        }
//    }
//    return 0;
//}


//void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
//    int c1 = m - 1, i = m + n - 1, c2 = n - 1;
//    for (; i >= 0; i--)
//    {
//        if (c1 < 0 || c2 < 0) break;
//        if (nums1[c1] <= nums2[c2])
//            nums1[i] = nums2[c2--];
//        else nums1[i] = nums1[c1--];
//    }
//
//        while (c2)
//            nums1[i--] = nums2[c2--];
//}
//
//
//int main()
//{
//    vector<int> n1, n2;
//    n1 = { 1,2,3,0,0,0 };  n2 = { 2,5,6 };
//    merge(n1,3,n2,3);
//    return 0;
//}

//#include<iostream>
//#include<vector>
//#include<string>
//using namespace std;
//const int N = 30;
//typedef pair<int, int> pii;
//int n;
//vector<int> p[N];
//pii find(int x)
//{
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < p[i].size(); j++)
//        {
//            if (p[i][j] == x)
//                return {i,j};
//        }
//    }
//}
//void clean(int x, int y)
//{
//    for (int j = y + 1; j < p[x].size(); j++)
//    {
//        int t = p[x][j];
//        p[t].push_back(t);
//    }
//    p[x].resize(y+1);
//}
//void move(int x1,int y1 ,int x2 )
//{
//    for (int j = y1; j < p[x1].size(); j++)
//    {
//        p[x2].push_back(p[x1][j]);
//    }
//    p[x1].resize(y1);
//}
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++)
//    {
//        p[i].push_back(i);
//    }
//    string op1, op2;
//    int a, b;
//    while (cin >> op1 >> a >> op2 >> b)
//    {
//        pii pa = find(a);
//        int x1 = pa.first, y1 = pa.second;
//        pii pb = find(b);
//        int x2 = pb.first, y2 = pb.second;
//        if (x1 == x2) continue;
//        if (op1 == "move")
//            clean(x1,y1);
//
//        if (op2 == "onto")
//            clean(x2,y2);
//
//        move(x1,y1,x2);
//    }
//
//    for (int i = 0; i < n; i++)
//    {
//        cout << i << ':';
//        for (int j = 0; j < p[i].size(); j++)
//        {
//            cout << " " << p[i][j];
//        }
//        cout << endl;
//    } 
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const  int N = 1e5 + 10, M = 1e6 + 10;
//int h, id, e[N], ne[N];
//int mp[M];
//int main()
//{
//    int q; cin >> q;
//    id ++ ;
//    e[id] = 1;
//    mp[1] = id;
//    while (q--)
//    {
//        int op, x, y;
//        cin >> op >> x;
//        int p = mp[x];
//        if (op == 1)
//        {
//            cin >> y;
//            id++;
//            e[id] = y;
//            ne[id] = ne[p];
//            ne[p] = id;
//            mp[y] = id;
//        }
//        else if (op == 2)
//        {
//            cout << e[ne[p]] << endl;
//        }
//        else
//        {
//            ne[p] = ne[ne[p]];
//        }
//    }
//    return 0;
//}
//
//
//
//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10, M = 1e6 + 10;
//int e[N]; int en[N];  int mp[M];
//int main()
//{
//    int id = 1;
//    int n; cin >> n; e[1] = 1; mp[1] = id;
//    while (n--)
//    {
//        int op, a; cin >> op >> a;
//        int p = mp[a];
//        if (op == 1)
//        {
//            int b; cin >> b; id++;
//            e[id] = b; mp[b] = id; en[id] = en[p]; en[p] = id;
//        }
//        else if (op == 2)
//        {
//            cout << e[en[p]] << endl;
//        }
//        else
//        {
//            
//                en[a] = en[en[a]];
//                  
//        }
//    }
//
//
//    return 0;
//}



//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int e[N], en[N], mp[N];  int id;
//int main()
//{
//    int n; cin >> n;
//    id++; e[id] = 1;  mp[1] = id;
//    for (int i = 2; i <= n; i++)
//    {
//        int k, p; cin >> k >> p;
//        if (p == 0)
//        {
//            id++;  e[id] = i;
//            mp[i] = id;
//            en[id] = mp[k];
//        }
//        else
//        {
//            id++; e[id] = i; mp[i] = id;
//            en[mp[k]] = id;
//        }
//    }
//    int m; cin >> m;
//    while (m--)
//    {
//        int x; cin >> x;
//        if (mp[x] == 0)
//            continue;
//
//    }
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int h; 
//int id;
//int e[N];
//int ne[N], pre[N], mp[N];
//
//void push_front(int x)  //头插
//{
//    id++;
//    e[id] = x;  
//    mp[x] = id;
//    pre[id] = h;
//    ne[id] = ne[h];
//
//    pre[ne[h]] = id;
//    ne[h] = id;
//}
//void print()
//{
//    for (int i = ne[h]; i; i = ne[i])
//    {
//        cout << e[i] << " ";
//    }
//    cout << endl << endl;
//}
//void insert_back(int p , int x)
//{
//    id++; e[id] = x;
//    mp[x] = id;  
//    ne[id] = ne[p]; pre[id] = p;
//
//    pre[ne[p]] = id;
//    ne[p] = id; 
//}
//void insert_front(int p, int x)
//{
//    id++; e[id] = x; mp[x] = id;
//    ne[id] = p;
//    pre[id] = pre[p];
//
//    ne[pre[p]] = id;
//    pre[p] = id;
//}
//void erase(int p)
//{
//    mp[e[p]] = 0;
//    ne[pre[p]] = ne[p];
//    pre[ne[p]] = pre[p];
//}
//int find( int x)
//{
//    return mp[x];
//}
//int main()
//{
//    for (int i = 1; i <= 5; i++)
//    {
//        push_front(i);
//        print();
//    }
//
//    erase(2);
//    print();
//    erase(4);
//    print();
//
//    return 0;
//}




//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int e[N], ne[N]; int pre[N], mp[N];
//int id; int h;
//int main()
//{
//    int n; cin >> n;
//    id++; e[id] = 1; mp[1] = id;  ne[h] = id;  pre[id] = h;
//    for (int i = 2; i <= n; i++)
//    {
//        int x, y; cin >> x >> y;
//        id++; e[id] = i; mp[i] = id;
//        if (y == 0) // zuo
//        {
//            ne[id] = x;  pre[id] = pre[x];
//
//            ne[pre[x]] = id;  pre[x] = id;
//        }
//        else//右
//        {
//            ne[id] = ne[x];
//            pre[id] = x;
//
//            pre[ne[x]] = id;
//            ne[x] = id;
//        }
//    }
//    int m; cin >> m;
//    while (m--)
//    {
//        int x; cin >> x;
//        if (mp[x] == 0) continue;
//
//        mp[x] = 0;
//
//        ne[pre[x]] = ne[x];
//        pre[ne[x]] = pre[x];
//    }
//
//    for (int i = ne[h]; i; i = ne[i])
//    {
//        cout << e[i] << " ";
//    }
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 111;
//int e[N], ne[N], mp[N];  int h, id;
//int main()
//{
//    int n, m; cin >> n >> m;
//     h = 1;
//    for (int i = 10; i >= 1; i--)
//    {
//        id++;  e[id] = i; mp[i] = id;
//        ne[id] = ne[h];
//        ne[h] = id;
//    }
//
//    for(int i = 1; i ;i+=3)
//
//    return 0;
//}


//const int N = 1e5 + 10;
//int h; 
//int id;
//int e[N], ne[N];  int mp[N];
//void push_front(int x)
//{
//    id++;  e[id] = x; mp[x] = id; ne[id] = ne[h];
//    ne[h] = id;
//}
//void print()
//{
//    for (int i = ne[h]; i; i = ne[i])
//        cout << e[i] << " ";
//}
//int find(int x)
//{
//    return mp[x];
//}
//
//void insert(int p, int x)
//{
//    id++;  e[id] = x; mp[x] = id;
//    ne[id] = ne[p];
//    ne[p] = id;
//}
//void erase(int p)
//{
//    if (ne[p] != 0)
//    {
//        mp[e[ne[p]]] = 0;
//        ne[p] = ne[ne[p]];
//    }
//}

//#include<iostream>
//using namespace std;
//const int N = 1e6 + 10;
//int n;
//int skt[N];
//void push(int x)
//{
//    skt[++n] = x;
//}
//
//void pop()
//{
//    --n;
//}
//
//int top()
//{
//    return skt[n];
//}
//bool empty()
//{
//    return n == 0;
//}
//int size()
//{
//    return n;
//}
//int main()
//{
//    for (int i = 0; i <= 10; i++)
//    {
//        push(i);
//    }
//    while (size())
//    {
//        cout << top() << " ";
//        pop();
//    }
//    return 0;
//}

//#include<iostream>
//#include<stack>
//using namespace std;
//int main()
//{
//    stack<int> s;
//    for (int i = 0; i <= 10; i++)
//    {
//        s.push(i);
//    }
//
//    while (!s.empty())
//    {
//        cout << s.top() << " ";
//        s.pop();
//    }
//    return 0;
//}
//#include<iostream>
//#include<vector>
//#include<stack>
//using namespace std;
//
//
//int main()
//{
//    int q; cin >> q;
//    while (q--)
//    {
//        int n; cin >> n;
//        vector<int> c1(n);  vector<int> c2(n);
//        for (int i = 0; i < n; i++)
//            cin >> c1[i];
//        for (int i = 0; i < n; i++)
//            cin >> c2[i];
//
//        stack<int> st;
//        for (int i = 0; i < n; i++)
//        {
//            st.push(c1[i]);  int j = 0;
//            while (j < n && !st.empty() && st.top() == c2[j])
//            {
//                st.pop(); j++;
//            }
//        }
//        if (st.size()) cout << "No" << endl;
//        else cout << "Yes" << endl;
//    }
//    return 0;
//}


//#include<iostream>
//#include<stack>
//#include<string>
//using namespace std;
//int main()
//{
//
//    stack<int> st;
//    int num = 0;
//    char ch;
//    while (cin >> ch)
//    {
//        if (ch == '@') break;
//        if (ch == '.')
//        {
//            st.push(num);
//            num = 0;
//        }
//        else if (ch >= '0' && ch <= '9')
//        {
//            num = num * 10 + (ch-'0');
//        }
//        
//        else
//        {
//            int r = st.top();
//            st.pop();
//            int l = st.top();
//            st.pop();
//            if (ch == '+')
//                st.push(l + r);
//            else if (ch == '-')
//                st.push(l - r);
//            else if (ch == '*')
//                st.push(l * r);
//            else
//                st.push(l / r);
//        }
//    }
//
//    cout << st.top() << endl;
//
//    return 0;
//}



//#include<iostream>
//#include<stack>
//#include<string>
//using namespace std;
//bool pi[111];
//int main()
//{
//    string s; cin >> s;
//    stack<int> st;
//    string ret;
//    for (int i = 0; i < s.size(); i++)
//    {
//        if (s[i] == '[' || s[i] == '(')
//            st.push(i);
//        else
//        {
//            if (st.empty()) continue;
//            if (s[i] == ']' && s[st.top()]== '[' || s[i] == ')' && s[st.top()] == '(')
//            {
//                pi[i] = pi[st.top()] = true;  st.pop();
//            }
//           
//        }
//    }
//    for (int i = 0; i < s.size(); i++)
//    {
//        if (pi[i])
//        {
//            ret += s[i];
//            continue;
//        }
//
//        if (s[i] == '(' || s[i] == ')')
//        {
//            ret += "()";
//        }
//        else if (s[i] == '['|| s[i] == ']')
//        {
//            ret += "[]";
//        }
//        
//    }
//    cout << ret << endl;
//        return 0;
//}

//const int N = 1e6 + 10;
//int h, t;
//int q[N];
//void push(int x)
//{
//    q[++t] = x;
//}
//void pop()
//{
//    h++;
//}
//int front()
//{
//    return q[h + 1];
//}
//int back()
//{
//    return q[t];
//}
//int size()
//{
//    return t - h;
//}
//bool empty()
//{
//    return t - h == 0;
//}
//int main()
//{
//    for (int i = 1; i <= 10; i++)
//    {
//        push(i);
//    }
//    while (size())
//    {
//        cout << front() << " " << back() << endl;
//        pop();
//    }
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 1e4 + 10;  int h, t; int q[N];
//void push(int x)
//{
//    q[++t] = x;
//}
//void pop()
//{
//    if (h == t) cout << "ERR_CANNOT_POP" << endl;
//    else
//    h++;
//}
//void query()
//{
//    if (h == t) cout << "ERR_CANNOT_QUERY" << endl;
//    else 
//    cout << q[h + 1] << endl;
//}
//void size()
//{
//    cout << t - h << endl;
//}
//int main()
//{
//    int n; cin >> n;
//    while (n--)
//    {
//        int op; cin >> op;
//        if (op == 1)
//        {
//            int x; cin >> x;
//            push(x);
//        }
//        else if (op == 2)
//        {
//            pop();
//        }
//        else if (op == 3)
//            query();
//        else
//            size();
//
//
//    }
//    return 0;
//}

//#include<iostream>
//#include<queue>
//
//using namespace std;//一个hh表  一个二维数组 一个队列 一个ret
//const int N = 1e5 + 10;
//int vis[N];
//int main()
//{
//    queue<pair<int, int>> q;
//    int n; cin >> n; int ret = 0;
//    while (n--)
//    {
//        int t, k; cin >> t >> k; 
//        for (int i = 0; i < k; i++)
//        {
//            int x; cin >> x;
//            q.push({ t,x });
//            if (vis[x] == 0)
//            {
//                ret++;
//            }
//            vis[x]++;
//        }
//        while (q.size() && q.back().first - q.front().first >= 86400)
//        {
//            int x = q.front().second;
//            if (vis[x] == 1) ret--;
//            vis[x]--;
//            q.pop();
//        }
//        cout << ret << endl;
//    }
//    return 0;
//}

//#include<iostream>
//#include<vector>
//using namespace std;
//const int N = 1e5 + 10;
//int n; 
//vector<int> edges[N];
//int main()
//{
//    cin >> n;
//    for (int i = 1; i < n; i++)
//    {
//        int a, b; cin >> a >> b;
//        edges[a].push_back(b);
//        edges[b].push_back(a);
//
//    }
//    return 0;
//}
//
//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int h[N], e[N * 2], ne[N * 2], id;
//int n;
//void add(int a,int b)
//{
//    id++;
//    e[id] = b;
//    ne[id] = h[a];
//    h[a] = id;
//}
//int main()
//{
//    cin >> n;
//    for (int i = 1; i < n; i++)
//    {
//        int a, b; cin >> a >> b;
//        add(a, b);  add(b,a);
//    }
//    return 0;
//}

//#include<iostream>
//#include<vector>
//#include<queue>
//using namespace std;
//const int N = 1e5 + 10;
//vector<int> edges[N];
//bool st[N];
//void dfs(int u)
//{
//    cout << u << " ";
//    st[u] = true;
//    for (auto e : edges[u])
//    {
//        if (!st[e]) dfs(e);
//    }
//}
//void bfs(int u)
//{
//    cout << u << " ";
//    st[u] = true;
//    queue<int> q;
//    q.push(u);
//    while (q.size())
//    {
//        int x = q.front();  q.pop();
//        for (auto e : edges[x])
//        {
//            if (st[e] == false)
//            {
//                cout << e << " ";
//                q.push(e);  st[e] = true;
//            }
//        }
//    }
//}
//int main()
//{
//    int n; cin >> n;
//    for (int i = 1; i < n; i++)
//    {
//        int a, b; cin >> a >> b;
//        edges[a].push_back(b);
//        edges[b].push_back(a);
//    }
//
//    //dfs(1);
//   // cout << endl;
//    bfs(1);
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int h[N];  int id;  int e[N * 2], ne[N * 2];
//bool st[N];
//void push(int a , int b)
//{
//    id++; e[id] = b;
//    ne[id] = h[a];
//    h[a] = id;
//}
//void dfs(int u)
//{
//    cout << u << " ";
//    st[u] = true;
//    for (int i = h[u]; i; i = ne[i])
//    {
//        int x = e[i];
//        if (st[x] == false)
//            dfs(x);
//    }
//}
//void bfs(int u)
//{
//    cout << u << " ";
//    st[u] = true;
//    queue<int> q;  q.push(u);
//    while (q.size())
//    {
//        int x = q.front();  q.pop();
//        for (int i = h[x]; i; i = ne[i])
//        {
//            if (st[e[i]] == false)
//            {
//                cout << e[i] << " ";
//                st[e[i]] = true;
//                q.push(e[i]);
//            }
//        }
//    }
//}
//int main()
//{
//    int n; cin >> n;
//    for (int i = 1; i < n; i++)
//    {
//        int a, b; cin >> a >> b;
//        push(a,b);
//        push(b,a);
//    }
//    //dfs(1);
//    bfs(1);
//    return 0;
//}


//#include<iostream>
//#include<string>
//using namespace std;
//string a, b;
//void dfs(int l1, int r1, int l2, int r2)
//{
//    if (l1 > r1) return;
//    int  p = l1;
//    while (b[p] != a[l2]) p++;
//
//    dfs(l1, p - 1, l2 + 1, l2 + p - l1);
//    dfs(p + 1, r1, l2 + p - l1 + 1, r2);
//
//    cout << a[l2];
//}
//int main()
//{
//    cin >> b >> a;
//    dfs(0, b.size()-1, 0, a.size()-1);
//    return 0;
//}


//#include<iostream>
//#include<queue>
//using namespace std;
//const int N = 111;
//int h[N], e[N * 2], ne[N * 2]; int id;
//bool st[N];  int fa[N]; int dist[N];
//void add(int a, int b)
//{
//    id++; e[id] = b; ne[id] = h[a]; h[a] = id;
//}
//void bfs(int u)
//{
//    int hh = 0;  int k = 0;  queue<int> q;
//    q.push(u); st[u] = true;
//    while (q.size())
//    {
//        int sz = q.size();  hh++; k = max(k, sz);
//        while (sz--)
//        {
//            int x = q.front(); q.pop();
//            for (int i = h[x]; i; i = ne[i])
//            {
//                if (st[e[i]] == false) q.push(e[i]);
//            }
//        }
//    }
//    cout << hh << endl; cout << k << endl;
//}
//int main()
//{
//    int n; cin >> n;
//    for (int i = 1; i < n; i++)
//    {
//        int a, b; cin >> a >> b;
//        add(a, b); fa[b] = a;
//    }
//    bfs(1);
//    int x, y; cin >> x >> y;
//    while (x != 1)
//    {
//        dist[fa[x]] = 1 + dist[x];
//        x = fa[x];
//    }
//    int len = 0;
//    while (y != 1 && dist[y] == 0)
//    {
//        len++;
//        y = fa[y];
//    }
//    cout << len + dist[y] * 2 << endl;
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int n; int heap[N];
//void up(int child)
//{
//    int parent = child / 2;
//    if (parent >= 1 && heap[child] > heap[parent])
//    {
//        swap(heap[child],heap[parent]);
//        child = parent; 
//        parent = child / 2;
//    }
//}
//void down(int parent)
//{
//    int child = max(heap[parent*2]);
//    
//
//}
//int main()
//{
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int heap[N]; int n;
//void up(int child)
//{
//    int parent = child / 2;
//    while (parent >= 1 && heap[child] <= heap[parent])
//    {
//        swap(heap[child],heap[parent]);
//        child = parent;
//        parent = child / 2;
//    }
//}
//void down(int parent)
//{
//    int child = parent * 2;
//    while (child <= n)
//    {
//        if (heap[child] <= heap[child + 1] && child + 1 <= n)
//            child++;
//        swap(heap[child],heap[parent]);
//        parent = child;
//        child = parent * 2;
//    }
//}
//void push(int x)
//{
//    n++; heap[n] = x;
//    up(n);
//}
//void pop()
//{
//    swap(heap[1], heap[n]); n--;
//    down(1);
//}
//int top()
//{
//    return heap[1];
//}
//int main()
//{
//    int n; cin >> n;
//    return 0;
//}



//#include<iostream>
//#include<queue>
//using namespace std;
//const int N = 1e4 + 10; 
//long long a[N], b[N], c[N];
//struct abc
//{
//    long long num, n, x;
//    bool operator < (const abc& x) const
//    {
//        return this->num > x.num;
//    }
//   
//};
//long long cal(long long i, long long x)
//{
//    return a[i] * x * x + b[i] * x + c[i];
//}
//int main()
//{
//    int n, m; cin >> n >> m;
//    priority_queue<abc> q;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> a[i] >> b[i] >> c[i];
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        q.push({cal(i,1),i,1});
//    }
//    while (m--)
//    {
//        abc xx = q.top();  q.pop();
//        long long num = xx.num, n = xx.n, x = xx.x;
//        cout << num << " ";
//        q.push({cal(n,x+1),n,x+1});
//    }
//    return 0;
//}


//#include<iostream>
//#include<queue>
//using namespace std;
//const int N = 1e5 + 10;
//long long a[N], b[N];
//struct abc
//{
//    long long num, i, j;
//    bool operator < (const abc& x) const
//    {
//        return num > x.num;
//    }
//};
//int main()
//{
//    int n; cin >> n;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i];
//    for (int i = 1; i <= n; i++)
//        cin >> b[i];
//    priority_queue<abc> q;
//    
//    for (int i = 1; i <= n; i++)
//    {
//        q.push({a[i]+b[1],i,1});
//    }
//    while (n--)
//    {
//        abc xx = q.top(); q.pop();
//        long long num = xx.num,i = xx.i,j = xx.j;
//        cout << num << " ";
//        q.push({a[i]+b[j+1],i,j+1});
//    }
//    return 0;
//}


//#include<iostream>
//#include<queue>
//#include<cstdlib>
//#include<vector>
//using namespace std;
//const int N = 2e5 + 10;
//int sex[N];
//int e[N];  int ne[N]; int pre[N];
//int id; int h;  
//
//bool st[N]; int nums[N];
//struct abc
//{
//    int num; 
//    int l, r;
//    bool operator < (const abc & x) const
//    {
//        if (num != x.num) return num > x.num;
//        else if (l != x.l)return l > x.l;
//        else return r > x.r;
//    }
//};
//
//int main()
//{
//    int n; cin >> n;
//    for (int i = 1; i <= n; i++)
//    {
//        char x; cin >> x; if (x == 'B') sex[i] = 1;
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> e[i];
//        ne[i] = i + 1;
//        pre[i] = i - 1;
//    }
//    pre[1] = 0;  ne[n] = 0;
//    priority_queue<abc> q;
//    for (int i = 1; i < n; i++)
//    {
//        if(sex[i] != sex[i+1])
//        q.push({abs(e[i]-e[i+1]),i,i+1});
//    }
//    vector<abc> ret;
//    while (q.size())
//    {
//        auto t = q.top(); q.pop();
//        if (!st[t.l] && !st[t.r])
//        {
//            ret.push_back(t);
//            st[t.l] = st[t.r] = true;
//        }
//        else continue;
//
//        int l = pre[t.l];  int r = ne[t.r];
//        ne[l] = r;  pre[r] = l;
//        if (l && r && sex[l] != sex[r])
//            q.push({abs(e[l]-e[r]),l,r});
//    }
//
//    cout << ret.size() << endl;
//    for (auto & e : ret)
//    {
//        cout << e.l << " " << e.r << endl;
//    }
//    return 0;
//}


//#include<iostream>
//#include<map>
//#include<string>
//using namespace std;
//bool check(char ch)
//{
//    if ((ch >= 'a' && ch <= 'z')||( ch >= 'A' && ch <= 'Z')|| (ch >= '0' && ch <= '9'))
//        return true;
//    else 
//    return false;
//}
//int main()
//{
//    map<string, int> mp;
//    int n, p; cin >> n >> p;
//    for (int i = 1; i <= n; i++)
//    {
//        string s; int x; cin >> s >> x;
//        mp[s] = x;
//    }
//    long long ret = 0;
//    char ch; string t = "";
//    while (scanf_s("%c", &ch) != EOF)
//    {
//        if (check(ch)) t += ch;
//        else
//        {
//            ret += mp[t] ;
//            t = "";
//        }
//
//    }
//
//    cout << ret%p << endl;
//    return 0;
//}

//#include<iostream>
//#include<set>
//using namespace std;
//set<int> mp; int INF = 1e7 + 10;
//int main()
//{
//    int n; cin >> n;
//    long long ret = 0;
//    cin >> ret; mp.insert(ret);
//    mp.insert(-INF); mp.insert(INF);
//    for (int i = 1; i < n ; i++)
//    {
//        int x; cin >> x;
//        auto t = mp.lower_bound(x);
//        auto tmp = t; tmp--;
//        ret += min(abs(*t-x),abs(*tmp-x));
//        mp.insert(x);
//    }
//
//    cout << ret << endl; 
//    return 0;
//}

//#include<iostream>
//#include<set>
//using namespace std;
//int main()
//{
//    set<long long> mp;
//    int n; cin >> n;   long long INF = 1e10 + 10;
//    mp.insert(-INF); mp.insert(INF);
//    while (n--)
//    {
//        long long a, b;
//        cin >> a >> b;
//        if (a == 1)
//        {
//            if (mp.count(b))
//                cout << "Already Exist" << endl;
//            else
//                mp.insert(b);
//         
//        }
//        else if (a == 2)
//        {
//            if (mp.size() == 2)
//                cout << "Empty" << endl;
//            else
//            {
//                auto t = mp.lower_bound(b);
//                auto tmp = t; tmp--;
//                if (abs(*tmp - b) <= abs(*t - b))
//                {
//                    cout << *tmp << endl;
//                    mp.erase(*tmp);
//                   
//                }
//                else
//                {
//                    cout << *t << endl;
//                    mp.erase(*t);
//                }
//            }
//        }
//    }
//
//    return 0;
//}

//#include<iostream>
//#include<unordered_map>
//#include<string>
//using namespace std;
//int main()
//{
//    unordered_map<string,int> mp;
//    int n; cin >> n;
//    while (n--)
//    {
//        int t;
//        cin >> t;
//        if (t == 1)
//        {
//            string s; cin >> s;
//            long long x; cin >> x;
//            mp[s] = x;
//            cout << "OK" << endl;
//        }
//        else if (t == 2)
//        {
//            string s; cin >> s;
//            if (mp.count(s))
//                cout << mp[s] << endl;
//            else cout << "Not found" << endl;
//        }
//        else if (t == 3)
//        {
//            string s; cin >> s;
//            if (mp.count(s))
//            {
//                mp.erase(s);
//                cout << "Deleted successfully" << endl;
//            }
//            else cout << "Not found" << endl;
//        }
//        else
//        {
//            cout << mp.size() << endl;
//        }
//    }
//    return 0;
//}

//#include<iostream>
//#include<unordered_set>
//using namespace std;
//int main()
//{
//    
//    int n; cin >> n;
//    while (n--)
//    {
//        int len; cin >> len;
//        unordered_set<int> mp;
//        for (int i = 1; i <= len; i++)
//        {
//            int x; cin >> x;
//            if (mp.count(x)) continue;
//            else
//            {
//                cout << x << " ";
//                mp.insert(x);
//            }
//        }
//        cout << endl;
//    }
//    return 0;
//}
//
//#include<iostream>
//#include<unordered_map>
//#include<set>
//using namespace std;
//int main()
//{
//    unordered_map<string , set<int>> mp;
//    int n; cin >> n;
//    for(int i = 1; i <= n ; i++)
//    {
//        int len; scanf_s("%d",&len);
//        for (int j = 1; j <= len; j++)
//        {
//            
//            string s; cin >> s;
//            mp[s].insert(i);
//        }
//    }
//    int t; cin >> t;
//    while (t--)
//    {
//        string ss; cin >> ss;
//        for (auto e : mp[ss])
//        {
//            cout << e << " ";
//        }
//        cout << endl;
//    }
//    return 0;
//}

//#include<iostream>
//#include<unordered_map>
//using namespace std;
//const int N = 1e6 + 10;
//int main()
//{
//    long long ret = 0;
//    long long e[N];
//    unordered_map<int, int> mp;
//    long long n, c; cin >> n >> c;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> e[i];
//        mp[e[i]]++;
//    }
//    for (int i = 1; i <= n; i++)
//        ret += mp[e[i] + c];
//
//    cout << ret << endl;
//    return 0;
//}

//#include<iostream>
//#include<string>
//#include<unordered_map>
//using namespace std;
//int main()
//{
//    unordered_map<string, int>mp;
//    int n; cin >> n;  long long ret = 0;
//    while (n--)
//    {
//        string s, t; cin >> s >> t;
//        s = s.substr(0,2);
//        if (s == t) continue;
//        ret += mp[t + s];
//        mp[s + t]++;
//    }
//    cout << ret << endl;
//    return 0;
//}


//#include<iostream>
//#include<cstring>
//using namespace std;
//const int N = 23, INF = 0x3f3f3f3f;
//int h[N];
//void init()
//{
//    memset(h,0x3f,sizeof h);
//
//}
//int f(int x)
//{
//    int idx = ((x % N) + N) % N;
//    while (h[idx] != INF && h[idx]!= x)
//    {
//        idx++;
//        if (idx == N) idx = 0;
//    }
//    return idx;
//}
//void insert(int x)
//{
//    int id = f(x);
//    h[id] = x;
//}
//bool find(int x)
//{
//    int id = f(x);
//    return h[id] == x;
//}
//int main()
//{
//    init();
//    return 0;
//}


//#include<iostream>
//#include<cstring>
//using namespace std;
//const int N = 23;
//int h[N];
//int e[N], ne[N],id;
//
//int f(int x)
//{
//    return ((x % N) + N) % N;
//}
//
//bool find(int x)
//{
//    int idx = f(x);
//    for (int i = h[idx]; i; i = ne[i])
//    {
//        if (e[i] == x) return true;
//    }
//    return false;
//}
//
//void insert(int x)
//{
//    if (find(x)) return;
//    int idx = f(x);
//    id++;
//    e[id] = x;
//    ne[id] = h[idx];
//    h[idx] = id;
//}

//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int n; int a[N];
//void insert_sort()
//{
//    for (int i = 2; i <= n; i++)
//    {
//        int key = a[i]; int j = i - 1;
//        while (j >= 1 && a[j] > a[j+1])
//        {
//            swap(a[j+1],a[j]);
//            j--;
//        }
//        
//    }
//}
//void select_sort()
//{
//    for (int i = 1; i < n; i++)
//    {
//        int key = i;
//        for (int j = i+1 ; j <= n; j++)
//        {
//            if (a[key] > a[j])
//                key = j;
//        }
//        swap(a[key],a[i]);
//    }
//}
//void bubble_sort()
//{
//    for (int i = n; i > 1; i--)
//    {
//        int f = 0;
//        for (int j = 1; j < n; j++)
//        {
//            if (a[j] > a[j + 1])
//            {
//                f = 1;
//                swap(a[j], a[j + 1]);
//            }
//        }
//        if (f == 0) break;
//    }
//}
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n ; i++)
//    {
//        cin >> a[i];
//    }
//    bubble_sort();
//    for (int i = 1; i <= n; i++)
//        cout << a[i] << " ";
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int n; int a[N];
//void down(int parent , int n)
//{
//    int child = parent * 2;
//    while (child <= n)
//    {
//        if (child+1 <= n && a[child] < a[child+1]) child++;
//        if (a[parent] >= a[child]) return;
//        swap(a[parent],a[child]);
//        parent = child;
//        child = parent * 2;
//    }
//}
//
//void heap_sort()
//{
//    for (int i = n / 2; i >= 1; i--)
//    {
//        down(i,n);
//    }
//
//    for (int i = n; i > 1; i--)
//    {
//        swap(a[i],a[1]);
//        down(1,i-1);
//    }
//
//}



//#include<iostream>
//using namespace std;
//const int N = 1e5+10;
//int a[N]; int n;
//void down(int parent , int len)
//{
//    int child = parent * 2;
//    while (child <= len)
//    {
//        if (child + 1 <= len && a[child + 1] > a[child]) child++;
//        if (a[parent] >= a[child]) return;
//
//        swap(a[parent] , a[child]);
//        parent = child;
//        child = parent * 2;
//    }
//}
//
//void heap_sort()
//{
//    for (int i = n/2; i; i--)
//    {
//        down(i,n);
//    }
//
//    for (int i = n; i; i--)
//    {
//        swap(a[i], a[1]);
//        down(1,i-1);
//    }
//}
//int main()
//{
//    cin >> n; 
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> a[i];
//    }
//    heap_sort();
//    for (int i = 1; i <= n; i++)
//    {
//        cout << a[i] <<" ";
//    }
//    return 0;
//}


//#include<iostream>
//#include<cmath>
//using namespace std;
//const int N = 1e5+10;
//int n; int a[N];
//int getrand(int l, int r)
//{
//    return (rand() % (r - l + 1) + l);
//}
//void merge(int left, int right)
//{
//    if (left >= right) return;
//    int l = left - 1; int r = right + 1;
//    int x = getrand(left, right); int i = left;
//    while (i < r)
//    {
//        if (a[i] > x) swap(a[i], a[--r]);
//        else if (a[i] == x) i++;
//        else swap(a[i++],a[++l]);
//    }
//
//    merge(left,l);
//    merge(r , right);
//}
//
//int main()
//{
//    srand(time(0));
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> a[i];
//    }
//
//    merge(1,n);
//    for (int i = 1; i <= n; i++)
//    {
//        cout << a[i] << " ";
//    }
//    
//    return 0;
//}
//
//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int n; int a[N]; int tmp[N];
//void merge(int left , int right)
//{
//    if (left >= right) return;
//    int mid = (left + right) >> 1;
//
//    merge(left , mid); 
//    merge(mid + 1, right);
//
//    int cur1 = left; int cur2 = mid + 1;  int i = left;
//    while (cur1 <= mid && cur2 <= right)
//    {
//        if (a[cur1] < a[cur2])
//            tmp[i++] = a[cur1++];
//        else tmp[i++] = a[cur2++];
//    }
//    while (cur1 <= mid) tmp[i++] = a[cur1++];
//    while (cur2 <= right) tmp[i++] = a[cur2++];
//
//    for (int j = left; j <= right; j++)
//        a[j] = tmp[j];
//}
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> a[i];
//    }
//    merge(1,n);
//    for (int i = 1; i <= n; i++)
//        cout << a[i] << " ";
//    return 0;
//}


//#include<iostream>
//#include<string>
//using namespace std;
//int main()
//{
//    int n; cin >> n; int f = 0; int x;
//    for (int i = n; i >= 0; i--)
//    {
//        cin >> x;
//        if (x > 0)
//        {
//            if (!f) f++;
//            else cout << "+";
//         
//            if (x != 1)
//                cout << x;
//            else if (x == 1 && i == 0)
//                cout << x;
//            if (i != 0)
//            {
//                cout << "x";
//                if (i != 1)
//                    cout << "^" << i;
//            }
//        }
//        else if(x < 0)
//        {
//             f++;
//             cout << "-";
//            
//            if (x != -1)
//                cout << abs(x);
//            else if (x == -1 && i == 0)
//                cout << abs(x);
//            if (i != 0)
//            {
//                cout << "x";
//                if (i != 1)
//                    cout << "^" << i;
//            }
//        }
//
//    }
//    return 0;
//}

//#include<iostream>
//using namespace std;
//int main()
//{
//    int n; cin >> n; int x;
//    for (int i = n; i >= 0; i--)
//    {
//        cin >> x;
//        if (x > 0 && i != n)
//        {
//            cout << "+";
//        }
//        else if (x < 0) cout << "-";
//
//        if (x != 0)
//        {
//            if (abs(x) != 1)
//                cout << abs(x);
//            else if (abs(x) == 1 && i == 0)
//                cout << abs(x);
//
//            if (i != 0)
//                cout << "x";
//            if (i != 1 && i != 0)
//                cout << "^" << i;
//        }
//    }
//    return 0;
//}


//#include<iostream>
//#include<vector>
//using namespace std;
//int dx[4] = {0,1,0,-1};
//int dy[4] = {1,0,-1,0};
//int main()
//{
//    int n; cin >> n;
//    vector<vector<int>> vv(n, vector<int>(n, 0));  int z = 0;
//    int x = 0, y = 0; int i = 1;
//    while( i <= n * n)
//    {
//       
//        vv[x][y] = i++;
//        int a = x + dx[z];
//        int b = y + dy[z];
//
//        if (a < 0 || a >= n || b < 0 || b >= n || vv[a][b])
//        {
//            z++;
//            if (z == 4) z = 0;
//            x += dx[z];
//            y += dy[z];
//        }
//        else { x = a; y = b; }
//        
//    }
//    for (i = 0; i < n; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            printf("%-3d",vv[i][j]);
//        }
//        printf("\n");
//    }
//    return 0;
//}

//#include<iostream>
//#include<string>
//using namespace std;
//string s;
//int check(int i)
//{
//    if (i == 0 || i == s.size()-1) return 0;
//    if ((s[i - 1] >= '0' && s[i - 1] <= '9') && (s[i + 1] >= '0' && s[i + 1] <= '9') && s[i - 1] < s[i + 1])
//        return 1;
//    else if (s[i - 1] >= 'a' && s[i - 1] <= 'z' && s[i + 1] >= 'a' && s[i + 1] <= 'z' && s[i - 1] < s[i + 1])
//        return 2;
//    else return 0;
//}
//int main()
//{
//    int aa, b, c;
//    cin >> aa >> b >> c;
//    cin >> s;
//    for (int i = 0; i < s.size(); i++)
//    {
//        if (s[i] == '-')
//        {
//            if (check(i) )
//            {
//                int x = check(i);
//                if (c == 1)
//                {
//                    for (char a = s[i - 1] + 1; a < s[i + 1]; a += 1)
//                    {
//                        if (aa == 3)
//                            for (int j = 1; j <= b; j++)
//                                cout << '*';
//                        else if(aa == 2 && x == 2)
//                        for (int j = 1; j <= b; j++)
//                        {
//                            cout << (char)(a - 32);
//                        }
//                        else for (int j = 1; j <= b; j++)
//                        {
//                            cout << a;
//                        }
//                    }
//                }
//                else
//                {
//                    for (char a = s[i + 1] - 1; a > s[i - 1]; a -= 1)
//                    {
//                        if (aa == 3)
//                            for (int j = 1; j <= b; j++)
//                                cout << '*';
//                        else if (aa == 2 && x == 2)
//                            for (int j = 1; j <= b; j++)
//                            {
//                                cout << (char)(a - 32);
//                            }
//                        else for (int j = 1; j <= b; j++)
//                        {
//                            cout << a;
//                        }
//                    }
//                }
//                
//            }
//           
//            else cout << s[i];
//        }
//
//        else cout << s[i];
//    }
//    return 0;
//}


//#include<iostream>
//#include<algorithm>
//#include<string>
//string s1, s2, ret;
//int cur1, cur2, d;
//using namespace std;
//int main()
//{
//    cin >> s1 >> s2;
//    reverse(s1.begin(),s1.end());
//    reverse(s2.begin(),s2.end());
//    while (cur1 < s1.size() || cur2 < s2.size())
//    {
//        int a = 0; int b = 0;
//        if (cur1 < s1.size())
//            a = s1[cur1++]-'0';
//        if (cur2 < s2.size())
//            b = s2[cur2++]-'0';
//        ret += ((a + b + d) % 10 + '0');
//        d = (a + b + d) / 10;
//        
//    }
//    while (d)
//    {
//        ret += d%10+'0';
//        d = d / 10;
//    }
//    reverse(ret.begin(),ret.end());
//    cout << ret << endl;
//    return 0;
//}

//#include<iostream>
//#include<algorithm>
//#include<string>
//using namespace std;
//long long cur1, cur2, d;
//bool cmp(string s1 , string s2)
//{
//    if (s1.size() > s2.size())
//        return false;
//    else if (s1.size() < s2.size())
//        return true;
//    else
//    {
//        if (s1 <= s2) return false;
//        else return true;
//    }
//}
//int main()
//{
//    string a, b; cin >> a >> b;  int f = 0;
//    if (cmp(a, b))
//    {
//        swap(a, b);
//        f = 1;
//    }
//    string ret;
//    reverse(a.begin(),a.end());
//    reverse(b.begin(),b.end());
//    while (cur1 < a.size() || cur2 < b.size())
//    {
//        long long x = 0; long long y = 0;
//        if (cur1 < a.size())
//            x = a[cur1++]-'0';
//        if (cur2 < b.size())
//            y = b[cur2++] - '0';
//        if (x + d >= y)
//        {
//            ret += (x - y + d) + '0';
//            d = 0;
//        }
//        else
//        {
//            ret += (x - y + 10 + d) + '0';
//            d = -1; 
//        }
//    }
//    while (ret.size() > 1 && ret.back() == '0')
//    {
//        ret. pop_back();
//    }
//    reverse(ret.begin(),ret.end());
//    if (f == 1)
//        cout << "-";
//    cout << ret << endl;
//    return 0;
//}

//#include<iostream>
//#include<string>
//using namespace std;
//const int N = 1e5 + 10;
//int a[N], b[N], c[N];
//int al, bl, cl;
//int main()
//{
//    string s1, s2;
//    cin >> s1>> s2;
//    al = s1.size(); bl = s2.size(); cl = al + bl;
//    for (int i = 0; i < al; i++)
//        a[al - 1 - i] = s1[i] - '0';
//    for (int i = 0; i < bl; i++)
//        b[bl - 1 - i] = s2[i] - '0';
//    for (int i = 0; i < al; i++)
//    {
//        for (int j = 0; j < bl; j++)
//        {
//            c[i + j] += a[i] * b[j];
//        }
//    }
//    for (int i = 0; i < cl; i++)
//    {
//        c[i + 1] += c[i] / 10;
//        c[i] %= 10;
//    }
//    while (cl > 1 && c[cl - 1] == 0)
//        cl--;
//    for (int i = cl-1; i >=0;i--)
//    {
//        cout << c[i];
//    }
//    return 0;
//}


//#include<iostream>
//#include<string>
//using namespace std;
//const int N = 1e5 + 10;
//int a[N], c[N];
//int main()
//{
//    string s; long long b;
//    cin >> s >> b;
//    int al = s.size();
//    for (int i = 0; i < al; i++)
//        a[al - 1 - i] = s[i] - '0';
//    int cl = al; long long t = 0;
//    for (int i = cl - 1; i >= 0; i--)
//    {
//        t = t * 10 + a[i];
//        c[i] = t / b;
//        t %= b;
//    }
//
//    while (cl > 1 && c[cl - 1] == 0) cl--;
//
//    for (int i = cl - 1; i >= 0; i--)
//        cout << c[i];
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 1e4 + 10;
//int a[N], b[N], c[N], d[N];
//bool check(int x1, int y1, int x2, int y2,int x,int y)
//{
//    if (x >= x1 && x <= x1 + x2 && y >= y1 && y <= y1 + y2) return true;
//    else return false;
//}
//int main()
//{
//    int n; cin >> n;
//    for (int i = 0; i < n; i++)
//    {
//        int aa, bb, cc, dd; cin >> aa >> bb >> cc >> dd;
//        a[i] = aa; b[i] = bb; c[i] = cc; d[i] = dd;
//    }
//    int x, y; cin >> x >> y; int f = 0;
//    for (int i = n - 1; i >= 0; i--)
//    {
//        if (check(a[i], b[i], c[i], d[i],x,y))
//        {
//            f = 1;
//            cout << i + 1;
//            break;
//        }
//    }
//    if (f == 0)
//        cout << -1;
//    return 0;
//}


//#include<iostream>
//#include<string>
//using namespace std;
//bool check(string s)
//{
//    int l = 0; int r = s.size() - 1;
//    while (l < r)
//    {
//        if (s[l] != s[r]) return false;
//        l++; r--;
//    }
//    return true;
//}
//int main()
//{
//    int a, b; cin >> a >> b; int ret = 0; int f = 0;
//    int day1 = a % 100; int month1 = a / 100 % 100; int year1 = a / 10000 % 10000;
//    int day2 = b % 100; int month2 = b / 100 % 100; int year2 = b / 10000 % 10000;
//    for (int year = year1; year <= year2; year++)
//    {
//        for (int month = 1; month <= 12; month++)
//        {
//            for (int day = 1; day <= 31; day++)
//            {
//                if (f == 0)
//                {
//                    f = 1;
//                    month = month1; day = day1;
//                }
//                if (year == year2 && month == month2 && day == day2)
//                {
//                    int x = year * 10000 + month * 100 + day;
//                    string s = to_string(x);
//
//                    if (check(s))ret++;
//                    cout << ret << endl;
//                    return 0;
//                }
//                if (month == 1 || month == 3 || month == 5 || month == 7 || month == 8 || month == 10 || month == 12)
//                    ;
//                else if (month == 2)
//                {
//
//                    if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0)
//                    {
//                        if (day > 29)break;
//                    }
//                    else if (day > 28) break;
//                }
//                else if (day > 30)break;
//
//                int x = year * 10000 + month * 100 + day;
//                string s = to_string(x);
//
//                if (check(s))ret++; 
//                
//
//            }
//        }
//    }
//  //  cout << ret << endl;
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 5e3+10;
//int mp[N][N];  
//int f[N][N];
//int main()
//{
//    int n, m;
//    cin >> n >> m;
//    while (n--)
//    {
//        int x, y,v; cin >> x >> y >> v;
//        mp[x + 1][y + 1] += v;
//    }
//    n = 5001;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= n; j++)
//        {
//            f[i][j] = f[i - 1][j] + f[i][j - 1] + mp[i][j] - f[i-1][j-1];
//        }
//    }
//    int ret = 0; 
//    m = min(m,n);
//    for (int x2 = m; x2 <= n; x2++)
//    {
//        for (int y2 = m; y2 <= n; y2++)
//        {
//            int x1 = x2 - m + 1;  int y1 = y2 - m + 1;
//            ret = max(ret, f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1]);
//        }
//    }
//    cout << ret << endl;
//    return 0;
//}
//


//#include<iostream>
//using namespace std;
//const int N = 5e3 + 10;
//int a[N][N], f[N][N];
//int main()
//{
//    int n, m;
//    cin >> n >> m;
//    while (n--)
//    {
//        int x, y, v;
//        cin >> x >> y >> v;
//        a[x+1][y+1] += v;
//    }
//    for (int i = 1; i < N; i++)
//    {
//        for (int j = 1; j < N; j++)
//        {
//            f[i][j] = f[i - 1][j] + f[i][j - 1] + a[i][j] - f[i - 1][j - 1];
//        }
//    }
//    int ret = 0;
//    for (int i = m; i < N; i++)
//    {
//        for (int j = m; j < N; j++)
//        {
//            ret = max(ret, f[i][j] - f[i - m][j] - f[i][j - m] + f[i - m][j - m]);
//        }
//    }
//    cout << ret << endl;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//long long a[N], b[N], c[N];  long long p[N]; long long f[N];  long long ci[N];
//long long n, m;
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= m; i++)
//        cin >> p[i];
//    
//    for (int i = 1; i < n; i++)
//        cin >> a[i] >> b[i] >> c[i];
//
//    for (int i = 1; i < m; i++)
//    {
//        if (p[i] > p[i + 1])
//        {
//            f[p[i + 1]]++;  f[p[i]]--;
//        }           
//        else
//        {
//            f[p[i]]++; f[p[i + 1]]--;
//        }
//    }
//    long long prev = 0;
//    for (int i = 1; i < n; i++)
//    {
//        ci[i] = f[i] + prev;
//        prev += f[i];
//    }
//    long long  ret = 0;
//    for (int i = 1; i < n; i++)
//    {
//        ret += min(ci[i]*a[i],b[i]*ci[i]+c[i]);
//    }
//    cout << ret << endl;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 1e3 + 10;
//int f[N][N]; int m, n;
//void insert(int x1, int y1, int x2, int y2, int v)
//{
//    f[x1][y1] += v; f[x2 + 1][y1] -= v; f[x1][y2 + 1] -= v; f[x2 + 1][y2 + 1] += v;
//}
//int main()
//{
//    cin >> n >> m;
//    while (m--)
//    {
//        int x1, x2, y1, y2, v;
//        cin >> x1 >> y1 >> x2 >> y2;
//        insert(x1,y1,x2,y2,1);
//
//    }
//
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= n; j++)
//        {
//            f[i][j] = f[i][j] + f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1];
//            cout << f[i][j] << " ";
//        }
//        cout << endl;
//    }
//    return 0;
//}

//#include<iostream>
//#include<cstring>
//using namespace std;
//const int N = 1e6 + 10;
//int a[N]; int n; int t;  int hh[N];
//int main()
//{
//    cin >> t;  
//    while (t--)
//    {
//        memset(a,0,sizeof(a));
//        memset(hh, 0, sizeof(hh));
//        cin >> n;
//        for(int i = 1; i <= n; i++)
//        {
//            cin >> a[i];
//        }
//        int l = 0; int maxx = 0;
//        for (int i = 1; i <= n; i++)
//        {
//            
//                hh[a[i]]++;
//                while (hh[a[i]] >= 2 && i > l )
//                {
//                    hh[a[++l]]--;
//                }
//            
//
//            maxx = max(maxx , i-l);
//        }
//        cout << maxx << endl;
//    }
//    
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 1e6 + 10;
//long long a[N]; long long n, m;  long long hh[N]; long long ll;
//int main()
//{
//    cin >> n >> m; long long l = 1; long long x = 0; long long len = n; 
//    for (int i = 1; i <= n; i++)
//        cin >> a[i];
//    for (int i = 1; i <= n; i++)
//    {
//        if (hh[a[i]]++ == 0)
//            x++;
//        while (x == m)
//        {
//            if (len > i - l + 1)
//            {
//                len = i - l + 1;
//                ll = l;
//            }
//            if (hh[a[l]]-- == 1)
//                x--;
//            l++;
//        }
//
//    }
//    cout << ll << " " << ll+len-1 << endl;
//    return 0;
//}



//#include<iostream>
//#include<string>
//using namespace std;
//int hh[300];
//int main()
//{
//    string s; cin >> s; int len = (int)s.size();  int l = 0;   int x = 0;
//    for (int i = 0; i < s.size(); i++)
//    {
//        if (hh[s[i]]++ == 0) x++;
//        while (x == 26)
//        {
//            len = min(len, i - l + 1);
//
//            if (hh[s[l]]-- == 1)x--;
//            l++;
//        }
//
//    }
//    cout << len << endl;
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//long long a[N]; long long n;
//int main()
//{
//    cin >> n;  long long sum = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> a[i]; sum += a[i];
//    }
//    long long l = 1; long long ret = 0;  long long k = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        k += a[i];
//        while (k*2 >= sum)
//        {
//            ret = max(ret,max(sum-k,k-a[i]));
//            k -= a[l++];
//        }
//    }
//    cout << ret << endl;
//    return 0;
//}

//#include<iostream>
//#include<vector>
//#include<algorithm>
//using namespace std;
//long long n, c;
//int main()
//{ 
//    cin >> n >> c;  long long ret = 0;
//    vector<long long> a(n+1);
//    for (long long i = 1; i <= n; i++)
//        cin >> a[i];
//    sort(a.begin(),a.end());
//    for (long long i = 1; i <= n; i++)
//    {
//        long long l = 1, r = n ;
//        //左
//        while (l < r)
//        {
//            long long mid = l + (r - l) / 2;
//            if (a[mid] >= a[i] + c) r = mid;
//            else l = mid + 1;
//        }
//        long long re;
//        if (a[l] == a[i] + c)
//            re = l;
//        else continue;
//
//        l = 1; r = n;
//        while (l < r)
//        {
//            long long mid = l + (r - l + 1) / 2;
//            if (a[mid] <= a[i] + c) l = mid;
//            else r = mid - 1;
//        }
//
//        ret += r - re + 1;
//    }
//    cout << ret << endl;
//    return 0;
//}



//#include<iostream>
//#include<vector>
//#include<algorithm>
//#include<cmath>
//using namespace std;
//int main()
//{
//    int n, m; cin >> n >> m;
//    vector<int> school(n);
//    vector<int> student(m);
//    for (int i = 0; i < n; i++)
//        cin >> school[i];
//    for (int i = 0; i < m; i++)
//        cin >> student[i];
//    sort(school.begin(),school.end());
//    long long ret = 0;
//    for (auto e : student)
//    {
//        int l = 0; int r = n - 1;
//        while (l < r)//左
//        {
//            int mid = l + (r - l)/2;
//            if (school[mid] >= e)r = mid ;
//            else l = mid + 1 ;
//        }
//        int x = school[l];
//
//        l = 0;  r = n - 1;
//        while (l < r)//左
//        {
//            int mid = l + (r - l + 1) / 2;
//            if (school[mid] <= e)l = mid ;
//            else r = mid - 1;
//        }
//        ret += min(abs(e - x), abs(e - school[r]));
//
//    }
//    cout << ret << endl;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int a[N]; int n, k;
//bool check(int mid)
//{
//    int m = 0;
//    for (int i = 0; i < n; i++)
//    {
//        m += a[i] / mid;
//    }
//    if (m >= k) return true;
//    else return false;
//}
//int main()
//{
//     cin >> n >> k;
//    long long sum = 0;
//    for (int i = 0; i < n; i++)
//    {
//        cin >> a[i]; sum += a[i];
//    }
//    if (sum < k)
//    {
//        cout << 0 << endl;
//        return 0;
//    }
//    int r = sum / k;
//    int l = 1;
//    while (l < r)
//    {
//        int mid = l + (r - l + 1)/2;
//        if (check(mid)) l = mid;
//        else r = mid - 1;
//    }
//
//    cout << r << endl;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 1e6 + 10;
//int a[N]; long long m; int n;
//bool check(int mid)
//{
//    long long x = 0;
//    for (int i = 0; i < n; i++)
//    {
//        if (a[i] - mid > 0)
//            x += a[i] - mid;
//    }
//    if (x >= m) return true;
//    else return false;
//}
//int main()
//{
//    cin >> n >> m;  int r = 0;
//    for (int i = 0; i < n; i++)
//    {
//        cin >> a[i];
//        r = max(r, a[i]);
//
//    }
//    int l = 0; r--;
//    while (l < r)
//    {
//        int mid = l + (r - l + 1)/2;
//        if (check(mid)) l = mid;
//        else r = mid - 1;
//    }
//
//    cout << r << endl;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 5e4 + 10;
//int a[N]; int n, m;
////int calc(int x)
////{
////    int ret = 0;
////    for (int i = 0; i <= n; i++)
////    {
////        int j = i + 1;
////        while (j <= n && a[j] - a[i] < x) j++;
////        ret += j - i - 1;
////        i = j - 1;
////    }
////    return ret;
////}
//
//int calc(int mid)
//{
//    int nums = 0;
//    int l = 0;  int i = 0;
//     for(; i <= n ; i++ )
//    {
//        if (a[i] - a[l] >= mid)
//        {
//            nums += (i - 1) - (l + 1) + 1;
//             l = i;
//        }
//    }
//     if (i != l)  nums += i - l - 1;
//    return nums;
//}
//int main()
//{
//    int len; cin >> len;
//    cin >> n >> m;  a[n + 1] = len;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i];
//
//    n++;
//    int l = 1; int r = len;
//
//
//  //  cout << calc(4) << endl;
//    while (l < r)
//    {
//        int mid = l + (r - l + 1)/2;
//        if (calc(mid) <= m) l = mid;
//        else r = mid - 1;
//    }
//    cout << r << endl;
//    return 0;
//}


//#include<iostream>
//#include<vector>
//#include<algorithm>
//using namespace std;
//int main()
//{
//    int n; cin >> n;
//    vector<int> v(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v[i];
//    }
//    sort(v.begin(),v.end());
//    int ret = 0;  int x = n / 2;
//    for (int i = 0; i < n; i++)
//    {
//        if (i != x)
//            ret += abs(v[x] - v[i]);
//    }
//    cout << ret << endl;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 2e5 + 10; int a[N];
//int main()
//{
//    int n; cin >> n; int sum = 0;  int maax = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> a[i];
//        if (sum + a[i] >= 0)
//            sum += a[i];
//        else
//            sum = 0;
//        maax = max(maax , sum);
//    }
//
//    cout << maax << endl;
//    
//
//    return 0;
//}

//#include<iostream>
//#include<vector>
//#include<algorithm>
//using namespace std;
//int main()
//{
//    int x; int n; cin >> x >> n; vector<int> v(n);
//    for (int i = 0; i < n; i++)
//        cin >> v[i];
//    sort(v.begin(),v.end());
//    int l = 0; int r = n - 1;
//    while (l < r)
//    {
//        if (v[l] + v[r] <= x)
//        {
//            l++;
//            n--;
//        }
//        r--;
//    }
//    cout << n << endl;
//    return 0;
//}

//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 1e3 + 10; 
//struct x
//{
//    int index;
//    int num;
//}row[N],col[N];
//bool cmp(x x1, x x2)
//{
//    return x1.num > x2.num;
//}
//bool cmp1(x x1 , x x2)
//{
//    return x1.index < x2.index;
//}
//int main()
//{
//    int n, m, k, l, d;
//    cin >> n >> m >> k >> l >> d;
//
//    for (int i = 1; i <= n; i++) row[i].index = i;
//    for (int i = 1; i <= m; i++) col[i].index = i;
//
//    while (d--)
//    {
//        int x1, x2, y1, y2;
//        cin >> x1 >> y1 >> x2 >> y2;
//        if (x1 == x2) row[min(y1, y2)].num++;
//        else if (y1 == y2) col[min(x1, x2)].num++;
//
//    }
//    sort(row+1 ,row+n+1,cmp);
//    sort(col+1, col + m+ 1, cmp);
//    sort(row + 1, row + l + 1, cmp1);
//    sort(col + 1, col + k + 1, cmp1);
//    for (int i = 1; i <= k; i++)
//        cout << col[i].index << " ";
//    cout << endl;
//    for (int i = 1; i <= l; i++)
//        cout << row[i].index << " ";
//    cout << endl;
//
//    return 0;
//}


//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 1e3 + 10;
//struct x
//{
//    int index;
//    int num;
//}row[N] ,col[N];
//bool cmp1(x x1 , x x2)
//{
//    return x1.num > x2.num;
//}
//bool cmp2(x x1, x x2)
//{
//    return x1.index < x2.index;
//}
//int main()
//{
//    int n, m, k, l, d;
//    cin >> n >> m >> k >> l >> d;
//    //初始化 这样我们就可以对每队交头接耳的同学统计行列的数目
//    for (int i = 1; i <= n; i++)
//        row[i].index = i;
//    for (int i = 1; i <= m; i++)
//        col[i].index = i;
//    //统计数目 若是纵坐标相同 横坐标相差1  若是横坐标相同 则纵坐标相差1 我们要选相较小的坐标进行统计 这是 因为这与最后输出的横纵线位置刚好一致
//    while (d--)
//    {
//        int x1, x2, y1, y2;
//        cin >> x1 >> y1 >> x2 >> y2;
//        if (x1 == x2) col[min(y1, y2)].num++;
//        else if (y1 == y2) row[min(x1, x2)].num++;
//    }
//    //接下来进行排序 第一次排序将横纵线中数量最多的优先隔开 优先输出  之后第二次对index进行排序 将index较小的优先排序输出 满足输出格式
//
//    sort(row + 1, row + n + 1, cmp1);
//    sort(col + 1, col + 1 + m, cmp1);
//
//    sort(row+1 , row+1+k, cmp2);
//    sort(col+1 , col+1+l,cmp2);
//
//    for (int i = 1; i <= k; i++)
//        cout << row[i].index << " ";
//        cout << endl;
//        for (int i = 1; i <= l; i++)
//            cout << col[i].index << " ";
//        cout << endl;
//    return 0;
//}


//#include<iostream>
//#include<algorithm>
//using namespace std;
//int n, m, k;  const int N = 20;   int sk;
//int a[N][N]; bool st[N][N];  long long s[N];
//long long hang(int j)
//{
//    long long sum = 0;
//    for (int i = 0; i < m; i++)
//    {
//        st[j][i] = true;
//        sum += a[j][i];
//    }
//    return sum;
//}
//bool cmp(int x1 , int x2)
//{
//    return x1 > x2;
//}
//long long lie()
//{
//    long long sum = 0;
//    for (int i = 0; i < m; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            if (st[j][i] == false) s[i] += a[j][i];
//        }
//    }
//    sort(s,s+m,cmp);
//    for (int i = 0; i < sk; i++)
//    {
//        sum += s[i];
//    }
//    return sum;
//}
//
//void calc()
//{
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < m; j++)
//            st[i][j] = false;
//    }
//}
//int main()
//{
//    cin >> n >> m >> k;  //存储
//    long long maxx = 0;
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < m; j++)
//        {
//            cin >> a[i][j];
//        }
//    }
//    //二进制枚举行
//
//    for (int i = 0; i < (1 << n); i++)
//    {
//        //需要重置st表
//        calc();
//        memset(s,0,sizeof s);
//        long long sum = 0;  sk = k;
//        for (int j = 0; j < n; j++)
//        {
//            if (sk == 0)
//                break;
//            if (i >> j & 1)
//            {
//                sk--;
//                sum += hang(j);
//            }
//        }
//
//        if (sk != 0)//开始列选择
//        {
//            sum+=lie();
//        }
//        maxx = max(maxx , sum);
//    }
//    cout << maxx << endl;
//    return 0;
//}

//#include<iostream>
//#include<string>
//#include<algorithm>
//using namespace std;
//const int N = 25;
//int n;  string s[N];
//bool cmp(string s1, string s2)
//{
//    int n1 = s1.size();  int n2 = s2.size();
//    if (n1 > n2)
//    {
//        string x = s1.substr(0,n2);
//        if (x == s2 && s1.back() <= s2[0])
//            return false;
//    }
//    else if (n2 > n1)
//    {
//        string x = s2.substr(0, n1);
//        if (x == s1 && s2.back() <= s1[0])
//            return true;
//    }
//    
//    return s1 > s2;
//}
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++)
//        cin >> s[i];
//    sort(s, s + n,cmp);
//    for (int i = 0; i < n; i++)
//        cout << s[i];
//
//    return 0;
//}

//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 1e5 + 10;
//struct cow
//{
//    int t;
//    int d;
//}a[N];
//bool cmp(cow x1 , cow x2)
//{
//    return x1.t * x2.d < x1.d * x2.t;
//}
//int main()
//{
//    long long sumd = 0;
//    int n;
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> a[i].t >> a[i].d;
//        sumd += a[i].d;
//    }
//    sort(a+1,a+1+n,cmp);
//    long long sum = 0;
//   
//    for (int i = 1; i < n; i++)
//    {
//        sum += (sumd - a[i].d) * 2 * a[i].t;
//        sumd -= a[i].d;
//    }
//    cout << sum << endl;
//    return 0;
//}

//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 5e4+10;
//struct cow
//{
//    int w;
//    int s;
//}a[N];
//bool cmp(cow x , cow y)
//{
//    return x.s + x.w < y.s + y.w;
//}
//int main()
//{
//    int n; cin >> n;  long long sum = 0;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i].w >> a[i].s;
//    sort(a+1,a+1+n,cmp);
//    long long ret = -1e9 - 10;
//    for (int i = 1; i <= n; i++)
//    {
//        
//        
//        ret = max(ret,sum-a[i].s);
//        sum += a[i].w;
//    }
//    cout << ret << endl;
//    return 0;
//}

//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 1e3 + 10;
////高精度问题
//struct x
//{
//    int l;
//    int r;
//}a[N];
//bool cmp(x x1, x x2)
//{
//    return max(1/x1.r,x1.l/x2.r) < max(1/x2.r,x2.l/x1.r);
//}
//int main()
//{
//    int n; cin >> n; 
//    long long sum; int x; cin >> sum >> x;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i].l >> a[i].r;
//    sort(a+1,a+1+n,cmp);
//         long long ret = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        ret = max(ret,sum/a[i].r);
//        sum *= a[i].l;
//    }
//    cout << ret << endl;
//    return 0;
//}

//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 1e6 + 10;
//struct x
//{
//    int l; int r;
//}a[N];  int n;
//bool cmp(x x1, x x2)
//{
//    return x1.l < x2.l;
//}
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i].l >> a[i].r;
//    sort(a+1, a+1+n,cmp);
//    int ret = 1; int r = a[1].r;
//    for (int i = 2; i <= n; i++)
//    {
//        int left = a[i].l;  int right = a[i].r;
//        if(left < r)
//        { 
//            r = min(r, right);
//        }
//        else
//        {
//            r = right;
//            ret++;
//        }
//    }
//    cout << ret << endl;
//    return 0;
//}

//#include<cmath>
//int main()
//{
//    double x = sqrt(18);
//    cout << x << endl;
//    double y = 4;
//    cout << (y < x) << endl;
//    return 0;
//}

//#include<iostream>
//#include<cmath>
//#include<algorithm>
//#include<cstring>
//using namespace std;
//const int N = 1e3 + 10;
//struct r
//{
//    double l, r;
//}a[N];
//bool cmp(r r1, r r2)
//{
//  return   r1.l < r2.l;
//} 
//int n;
//double d = 1;
//int main()
//{
//    int nn = 1;
//    while (true)
//    {
//        cin >> n >> d;
//        if (n == 0 && d == 0) break;
//        memset(a, 0, sizeof a); bool f = false;
//        for (int i = 1; i <= n; i++)
//        {
//            转换为一维区间
//            double x, y; cin >> x >> y;
//            if (d < y) f = true;
//            a[i].l = x - sqrt(d * d - y * y);
//            a[i].r = x + sqrt(d * d - y * y);
//        }
//        if (f)
//        {
//            cout << "Case " << nn << ": " << -1 << endl;
//            nn++;
//            
//        }
//        else
//        {
//
//            sort(a + 1, a + 1 + n, cmp);
//            int sum = 1;  double r = a[1].r;
//            for (int i = 2; i <= n; i++)
//            {
//                double left = a[i].l;  double right = a[i].r;
//                if (r >= left)
//                {
//                    r = min(r, right);
//                }
//                else
//                {
//                    r = right;
//                    sum++;
//                }
//            }
//            cout << "Case " << nn << ": " << sum << endl;
//            nn++;
//        }
//    }
//    return 0;
//}


//#include<iostream> //这里的最小时间是指已经在牛棚中产奶的牛的最小结束时间  是要与所有正在产奶的牛比较而不是只是与当前进来的奶牛比
//#include<algorithm>
//#include<queue>//通过优先队列对这个最小结束牛棚进行维护
//using namespace std;
//const int N = 5e4 + 10;
//struct cow
//{
//    int l, r; 
//    int id;
//
//    bool operator <(cow x) const
//    {
//        return r > x.r;
//    }
//}a[N]; int n;  
//int b[N]; // 如何记录牛棚编号
//bool cmp(cow x , cow y)
//{
//    return x.l < y.l;
//}
//priority_queue<cow> q;
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> a[i].l >> a[i].r;
//        a[i].id = i;
//    }
//    
//    sort(a + 1, a + 1 + n, cmp);
//    
//    int ret = 1; b[a[1].id] = 1;
//    q.push(a[1]);    int cnt = 2;
//    int prev = 1;
//    for (int i = 2; i <= n; i++)
//    {
//        int l = a[i].l;  int r = a[i].r;
//        if (l <= q.top().r)
//        {
//            ret++; 
//            q.push(a[i]);
//            b[a[i].id] = cnt++;
//        }
//        else
//        {
//            b[a[i].id] = b[q.top().id];
//            q.pop();
//            q.push(a[i]);
//        }
//
//    }
//   
//
//
//
//    cout << ret << endl;
//    for (int i = 1; i <= n; i++)
//        cout << b[i] << endl;
//    return 0;
//}


//#include<iostream>  //一个结构体维护奶牛的左右区间   需要一个数组来存储   需要一个数组来村防晒霜 需要排序  两个都需要
//#include<algorithm>
//using namespace std;
//const int N = 3e3 + 10;
//struct cow 
//{
//    int l, r;
//}a[N];
//struct fang
//{
//    int x, num;
//}b[N];
//bool cmp1(cow x1 , cow x2)
//{
//    return x1.l > x2.l;
//}
//bool cmp2( fang x1 , fang x2)
//{
//    return x1.x > x2.x;
//}
//int c, m; 
//int main()
//{
//    cin >> c >> m;
//    for (int i = 1; i <= c; i++)
//        cin >> a[i].l >> a[i].r;
//    for (int i = 1; i <= m; i++)
//        cin >> b[i].x >> b[i].num;
//    sort(a+1 , a+1+c , cmp1);
//    sort(b + 1, b + 1 + m, cmp2);
//    int ret = 0;
//    for (int i = 1; i <= c; i++)
//    {
//        int l = a[i].l;  int r = a[i].r;
//        for (int j  =1 ; j <= m ; j++)
//        {
//            int x = b[j].x;  int num = b[j].num;
//            if (num == 0) continue;
//            if (x > r) continue;
//            if (x < l) break;
//
//            
//
//            b[j].num--;
//            ret++;
//            break;
//        }
//    }
//    cout << ret << endl;
//    return 0;
//}

//#include<iostream>
//#include<cmath>
//using namespace std;
//long long  a, b, p;
//long long qpow(long long a, long long b ,long long p)
//{
//    long long ret = 0;
//    while (b)
//    {
//        if (b & 1) ret = ret %p+ a % p;
//        a = a %p+ a % p;
//        b >>= 1;
//    }
//    return ret;
//}
//int main()
//{
//    
//    cin >> a >> b >> p;
//    
//    
//    cout << qpow(a,b,p) << endl;
//    return 0;
//}

//#include<iostream>
//#include<unordered_map>
//#include<algorithm>
//
//using namespace std;
//const int N = 2e4 + 10;
//struct lr
//{
//    int l, r;
//}; lr a[N]; int b[N*2];
//int n; int pos = 0;
//unordered_map<int , int> mp;
//int f[N*2];
//
//void lisan()
//{
//    pos = unique(b+1,b+1+pos)-(b+1);
//    sort(b + 1, b + 1 + pos);  int cnt = 1;
//    for (int i = 1; i <= pos; i++)
//    {
//        if (mp.count(b[i])) continue;
//        mp[b[i]] = cnt++;
//    }
//}
//bool cmp(lr x1, lr x2)
//{
//    return x1.l < x2.l;
//}
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> a[i].l >> a[i].r;
//        b[++pos] = a[i].l;
//        b[++pos] = a[i].r;
//    }
//    lisan();
//
//    for (int i = 1; i <= n; i++)
//    {
//        int left = a[i].l; int right = a[i].r;
//        f[mp[left]] += 1;
//        f[mp[right]] -= 1;
//    }
// 
//    for (int i = 1; i <= pos; i++)
//    {
//        f[i] += f[i - 1];
//    }
//    int sum = 0;
//    for (int i = 1; i <= pos; i++)
//    {
//        int j = i;
//        while (j <= pos && f[j] > 0)
//        {
//            j++;
//           
//        }
//        sum += b[j] - b[i];
//        i = j;
//    }
//    cout << sum << endl;
//    return 0;
//}


//#include<iostream>
//#include<unordered_map>
//#include<cmath>
//#include<algorithm>
//using namespace std;
//const int N = 2e4 + 10;
//struct lr
//{
//    long long l, r;
//}; lr a[N]; long long b[N*2];
//int n; int pos = 0;
//unordered_map<long long, long long> mp;
//
//
//
//void lisan()
//{
//    sort(b + 1, b + 1 + pos); 
//    pos = unique(b + 1, b + 1 + pos) - (b + 1);
//    int cnt = 1;
//    for (int i = 1; i <= pos; i++)
//    {
//        if (mp.count(b[i])) continue;
//        mp[b[i]] = cnt++;
//
//    }
//}
//bool cmp(lr x1, lr x2)
//{
//    return x1.l < x2.l;
//}
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> a[i].l >> a[i].r;
//        b[++pos] = a[i].l;
//        b[++pos] = a[i].r;
//    }
//    lisan();
//
//    long long sum = 0;
//    sort(a + 1, a + 1 + n, cmp);
//    int r = mp[a[1].r];  int l = mp[a[1].l];
//    for (int i = 2; i <= n; i++)
//    {
//        int left = mp[a[i].l];  int right = mp[a[i].r];
//        if (r >= left)
//        {
//            r = max(r, right);
//        }
//        else
//        {
//            sum += b[r] - b[l];
//            l = left;
//            r = right;
//        }
//    }
//    sum += b[r] - b[l];
//
//    cout << sum << endl;
//    return 0;
//}

//#include<iostream>
//#include<algorithm>
//#include<unordered_map>
//using namespace std;
//const int N = 1e7 + 10;
//int a[1010], b[1010];
//int disc[2010];
//int n, m;  int pos;  int cnt = 1;
//int hh[N];
//unordered_map<int,int>q;
//unordered_map<int,int> mm;
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= m; i++)
//    {
//        cin >> a[i] >> b[i];
//        disc[++pos] = a[i];
//        disc[++pos] = b[i];
//    }
//    sort(disc +1, disc+1+pos);
//    pos = unique(disc+1,disc+1+pos)-(disc+1);
//    for (int i = 1; i <= pos; i++)
//    {
//        if (q.count(disc[i])) continue;
//        
//        q[disc[i]] = cnt++;
//        q[disc[i] + 1] = cnt++;
//    }
//    
//    for (int i = 1; i <= m; i++)
//    {
//        for (int j = q[a[i]]; j <= q[b[i]]; j++)
//        {
//            
//                hh[j] = i; 
//        }
//    }
//    for(int i = 1; i <= n ; i++)
//        if (hh[i] != 0)
//        {
//            mm[hh[i]]++;
//        }
//
//    cout << mm.size() << endl;
//    return 0;
//}

//#include<iostream>
//#include<vector>
//#include<cstdio>
//using namespace std;
//char a, b, c;  int n;
//
//void hanno(int x,vector<int>&aa,vector<int> & bb,vector<int> &cc,char aaa,char bbb, char ccc)
//{
//    if (x == 1)
//    {
//        printf("%c->%d->%c\n",aaa,x,ccc);
//        cc.push_back(aa.back());
//        aa.pop_back();
//        return;
//    }
//    hanno(x-1,aa,cc,bb,aaa,ccc,bbb);
//    printf("%c->%d->%c\n", aaa, x, ccc);
//    cc.push_back(aa.back());
//    aa.pop_back();
//    hanno(x-1,bb,aa,cc,bbb,aaa,ccc);
//}
//int main()
//{
//    vector<int> aa, bb, cc;
//
//    cin >> n >> a >> b >> c;
//    for (int i = n; i >= 1; i-- )
//        aa.push_back(i);
//    hanno(n,aa,cc,bb,a,c,b);
//    return 0;
//}


//#include<iostream>
//#include<map>
//using namespace std;
//char a[14][5];
//int hh[13];
//int n[13];
//map<char, int> mp = { {'A',1},{'2',2},{'3',3},{'4',4},{'5',5},{'6',6},{'7',7},{'8',8},{'9',9},{'0',10},{'J',11},{'Q',12},{'K',13} };
//void dfs(int x)
//{
//    if (x == 13) return;
//    hh[x]++;
//    int xx = mp[a[x][n[x]--]];
//    dfs(xx);
//}
//int main()
//{
//    for (int i = 1; i <= 12; i++)
//        n[i] = 4;
//    for (int i = 1; i <= 13; i++)
//        for (int j = 1; j <= 4; j++)
//            cin >> a[i][j];
//    for (int i = 1; i <= 4; i++)
//        dfs(mp[a[13][i]]);
//
//    int ret = 0;
//    for (int i = 1; i <= 12; i++)
//        if (hh[i] == 4) ret++;
//    
//    cout << ret << endl;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 5e5 + 10;
//int a[N];  int n;  int tmp[N];//归并是从新排序可以吧内容放进另一个数组中
//long long dfs(int l,  int r)//这里排序并且统计完成后要把tmp中的内容拷贝给a 用于下一次比较统计 首先比较  当有一方到d达边界后 在将另一方全部放入数组中
//{
//    long long ret = 0;
//    if (l >= r) return 0;
//    
//    int mid = l + (r - l) / 2;
//   ret+=  dfs(l,mid);
//   ret+=  dfs(mid+1,r);
//   int left = l;  int right = mid + 1;  int i = left;
//   while (left <= mid && right <= r)
//   {
//       if (a[left] <= a[right])
//       {
//           tmp[i++] = a[left++];
//       }
//       else
//       {
//           ret += mid - left+1;
//           tmp[i++] = a[right++];
//       }
//   }
//   while (left <= mid) tmp[i++] = a[left++];
//   while (right <= r) tmp[i++] = a[right++];
//   for (int j = l; j <= r; j++)
//       a[j] = tmp[j];
//   return ret;
//}
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i];
//    long long r = dfs(1,n);
//    printf("%lld\n",r);
//    return 0;
//}

//#include<iostream>
//using namespace std;
//
//const int N = 5e6 + 10;
//int a[N]; int tmp[N]; int n; int k;
//void dfs(int l, int r)
//{
//    if (l >= r) return;
//    int mid = l + (r - l) / 2;
//    dfs(l,mid);
//    dfs(mid+1,r);
//     int cur1 = l;  int cur2 = mid+1;
//     int i = cur1;
//    while (cur1 <= mid && cur2 <= r)
//    {
//        if (a[cur1] <= a[cur2]) tmp[i++] = a[cur1++];
//        else tmp[i++] = a[cur2++];
//    }
//    while (cur1 <= mid) tmp[i++] = a[cur1++];
//    while (cur2 <= r) tmp[i++] = a[cur2++];
//    for (int j = 1; j <= r; j++)
//        a[j] = tmp[j];
//}
//int main()
//{
//    cin >> n >> k;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i];
//    dfs(1,n);
//    for (int i = 1; i <= n; i++)
//        if (i - 1 == k) cout << a[i] << endl;
//    return 0;
//}

//#include<iostream>
//#include<ctime>
//using namespace std;
//const int N = 5e6 + 10;
//int a[N];  int n, k;
//int randomm(int l ,int r)
//{
//    return a[rand() % (r-l+1)+l];
//}
//void dfs(int l, int r)
//{
//    if (l >= r) return;
//    int kk = randomm(l, r);
//    int left = l-1;  int right = r+1;  int i = l;
//
//
//    while (i < right)//这里是i < right 一定不能写成 left < right
//    {
//        if (a[i] < kk) swap(a[i++], a[++left]);
//        else if (a[i] == kk)i++;
//        else swap(a[i], a[--right]);
//    }
//
//    dfs(l,left);
//    dfs(right,r);
//}
//int main()
//{
//    srand(time(0));
//    scanf("%d %d",&n, &k);
//    for (int i = 1; i <= n; i++)
//        scanf("%d" , &a[i]);
//    dfs(1 , n);
//    printf("%d",a[k+1]);
//    return 0;
//}


//#include <iostream>
//#include <ctime>
//using namespace std;
//
//const int N = 5e6 + 10;
//int a[N];
//
//// 随机生成一个区间 [l, r] 内的整数
//int randomm(int l, int r) {
//    return rand() % (r - l + 1) + l;
//}
//
//// 快速排序的三路划分实现
//void quickSort(int l, int r) {
//    if (l >= r) return;
//
//    int mid = randomm(l, r); // 随机选择一个主元
//    int left = l - 1, right = r + 1, i = l;
//    int pivot = a[mid];
//
//    while (i < right) {
//        if (a[i] < pivot) swap(a[i++], a[++left]);
//        else if (a[i] == pivot) i++;
//        else swap(a[i], a[--right]);
//    }
//
//    // 递归排序左右两部分
//    quickSort(l, left);
//    quickSort(right, r);
//}
//
//int main() {
//    srand(time(0));
//    int n, k;
//    cin >> n >> k;
//    for (int i = 1; i <= n; i++) cin >> a[i];
//
//    // 调用快速排序
//    quickSort(1, n);
//
//    // 输出第 k 小的元素
//    cout << a[k+1] << endl;
//
//    return 0;
//}

//#include<iostream>
//#include<vector>
//using namespace std;
//vector<char> path;
//vector<vector<char>> ret;
//int n;
//void dfs()
//{
//    if (path.size() == n)
//    {
//        ret.push_back(path);
//        return;
//    }
//    path.push_back('N');
//    dfs();
//    path.pop_back();
//
//    path.push_back('Y');
//    dfs();
//    path.pop_back();
//}
//int main()
//{
//     cin >> n;
//    dfs();
//    for (auto e : ret)
//    {
//        for (auto h : e)
//            cout << h;
//            cout << endl;
//    }
//    return 0;
//}//nn ny  yn yy


//#include<iostream>
//#include<vector>
//using namespace std;
//int n; vector<int> path;
//vector<vector<int>> ret;
//bool st[20];
//void dfs(int pos)
//{
//    if (path.size() == n)
//    {
//        ret.push_back(path);
//        return;
//    }
//    for (int i = 1; i <= n; i++)
//    {  
//        if (st[i] == false)
//        {
//            path.push_back(i); st[i] = true;
//            dfs(i);
//            path.pop_back(); st[i] = false;
//        }
//    }
//}
//int main() 
//{
//    cin >> n;
//    dfs(1);
//    for (auto e : ret)
//    {
//        for (auto h : e)
//            printf("%5d",h);
//        cout << endl;
//    }
//    return 0;
//}
//


//#include<iostream>
//#include<cmath>
//using namespace std;
//int ret; int n, m;  long long sum;
//const int N = 25;
//int a[N];  int num ;
//bool st[N];
//bool issu(long long sum)
//{
//    for (int i = 2; i < sqrt(sum); i++)
//    {
//        if (sum % i == 0) return false;
//    }
//    return true;
//}
//void dfs(int pos)
//{
//    if (num == m && issu(sum))
//    {
//        ret++;
//        return;
//    }
//    for (int i = pos ; i <= n ; i++)
//    {
//        if (st[i] == false)
//        {
//            sum += a[i]; st[i] = true; num++;
//            dfs(i);
//            sum -= a[i]; st[i] = false; num--;
//        }
//    }
//}
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i];
//
//    dfs(1);
//
//    cout << ret << endl;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//int t[15], d[15], l[15]; int n;  int ret;
//bool st[15]; int num;
//void dfs(int pos,int nt)
//{
//    if (num == n) {
//        ret = 1;
//        return;
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        if (st[i] == false)
//        {
//            if ( nt <= d[i]+t[i])
//            {
//                num++;
//                st[i] = true;
//                if (nt < t[i])
//                    dfs(i,t[i]+l[i]);
//                else
//                dfs(i, l[i] + nt);
//                num--;
//                st[i] = false;
//            }
//            else
//            {
//                return;
//            }
//        }
//    }
//}
//int main()
//{
//    int m;
//    cin >> m;
//    while (m--)
//    {
//        ret = 0;
//        cin >> n;
//        for (int i = 1; i <= n; i++)
//            cin >> t[i] >> d[i] >> l[i];
//        dfs(1,0);
//        if (ret == 1) cout << "YES" << endl;
//        else cout << "NO" << endl;
//    }
//    return 0;
//}

//#include<iostream>
//#include<vector>
//#include<cmath>
//using namespace std;
//int n;  bool st[15];  int ret;
//vector<int> path; bool stcol[30]; bool strow[30];
//vector<vector<int>>r;
//void dfs(int pos,int nx)
//{
//    if (n+1 == nx)
//    {
//        ret++;
//        if (r.size() < 3) r.push_back(path);
//        return;
//    }
//
//    for (int i = 1; i <= n; i++)
//    {
//        if (st[i] == false  && !stcol[nx - i+n] && !strow[nx+i])
//        {
//            st[i] = true; strow[nx + i] = true;
//            stcol[nx - i+n] = true;
//            path.push_back(i);
//            dfs(i+1, nx + 1);
//            st[i] = false; strow[nx + i] = false; 
//            stcol[nx - i+n] = false;
//            path.pop_back();
//        }
//       
//    }
//}
//int main()
//{
//    cin >> n;
//    dfs(1,1);
//
//    for (auto e : r)
//    {
//        for (auto h : e)
//            cout << h << " ";
//        cout << endl;
//    }
//    cout << ret << endl;
//    return 0;
//}

//
//#include<iostream>
//using namespace std;
//int a[9][9]; bool col[9][10]; bool row[9][10]; bool st[3][3][10];
//bool dfs(int x , int y)
//{
//     
//        if (y == 9)
//        {
//            y = 0;
//            x++;
//        }
//        
//
//        if (x == 9)
//        {
//            return true;
//        }
//
//        if(a[x][y])
//        return dfs(x,y+1);
//    
//    for (int i = 1; i <= 9 ; i++)
//    {
//        if(!col[x][i] && !row[y][i] && !st[x/3][y/3][i])
//        {
//            a[x][y] = i;
//            col[x][i] = row[y][i] = st[x / 3][y / 3][i] = true;
//           
//           if( dfs(x,y+1)) return true;
//            a[x][y] = 0;
//            col[x][i] = row[y][i] = st[x / 3][y / 3][i] = false;
//
//        }
//    }
//    return false;
//}
//int main()
//{
//    for (int i = 0; i < 9; i++)
//    {
//        for (int j = 0; j < 9; j++)
//        {
//            int x;
//            cin >> x;
//            if (x) st[i / 3][j / 3][x] = row[j][x] = col[i][x] = true;
//            a[i][j] = x;
//        }
//    }
//    dfs(0,0);
//
//    for (int i = 0; i < 9; i++)
//    {
//        for (int j = 0; j < 9; j++)
//            cout << a[i][j] << " ";
//        cout << endl;
//    }
//    return 0;
//}


//#include <iostream>
//using namespace std;
//
//int a[10][10];
//bool col[10][10] = { false };
//bool row[10][10] = { false };
//bool st[4][4][10] = { false };
//
//bool dfs(int x, int y) {
//    if (y == 10) {
//        y = 1;
//        x++;
//    }
//
//    if (x == 10) {
//        return true;
//    }
//
//    if (a[x][y]) {
//        return dfs(x, y + 1);
//    }
//
//    for (int i = 1; i <= 9; i++) {
//        if (!col[x][i] && !row[y][i] && !st[x / 3][y / 3][i]) {
//            a[x][y] = i;
//            col[x][i] = row[y][i] = st[x / 3][y / 3][i] = true;
//
//            if (dfs(x, y + 1)) {
//                return true;
//            }
//
//            a[x][y] = 0;
//            col[x][i] = row[y][i] = st[x / 3][y / 3][i] = false;
//        }
//    }
//    return false;
//}
//
//int main() {
//    for (int i = 1; i <= 9; i++) {
//        for (int j = 1; j <= 9; j++) {
//            cin >> a[i][j];
//            if (a[i][j]) {
//                col[i][a[i][j]] = true;
//                row[j][a[i][j]] = true;
//                st[i / 3][j / 3][a[i][j]] = true;
//            }
//        }
//    }
//
//    if (dfs(1, 1)) {
//        for (int i = 1; i <= 9; i++) {
//            for (int j = 1; j <= 9; j++) {
//                cout << a[i][j] << " ";
//            }
//            cout << endl;
//        }
//    }
//  
//
//    return 0;
//}


//#include<iostream>
//using namespace std;
////#include<vector>
////vector<int> path;
////vector<vector<int>> r;
//int n, k; int sum; int ret;
//void dfs(int pos , int num)
//{
//    if (num == k)
//    {
//        if (n == sum)
//        {
//            ret++;
//           // r.push_back(path);
//        }
//        return;
//    }
//    for (int i = pos; i <= n-k+1; i++)
//    {
//        if ((k-num)*i <= (n-sum))
//        {
//
//            sum += i; num++;
//            dfs(i, num);
//            sum -= i; num--;
//            //path.pop_back();
//        }
//        else return;
//    }
//}
//int main()
//{
//    cin >> n >> k;
//    dfs(1,0);
//
//    cout << ret << endl;
//  /*  for (auto e : r)
//    {
//        for (auto h : e)
//            cout << h << " ";
//        cout << endl;
//    }*/
//    return 0;
//}

//#include<iostream>
//#include<algorithm>
//using namespace std;
//
//int n, w;
//const int N = 19;
//long long sum[N]; int cnt ;
//int a[N];   int r = 20; 
//
//void dfs(int pos)
//{
//    if (cnt >= r) return;
//    if (pos == n + 1)
//    {
//        r = cnt;
//        return;
//    }
//    for (int i = 1; i <= cnt; i++)
//    {
//        if (sum[i] + a[pos] > w) continue;
//        sum[i] += a[pos];
//        dfs(pos+1);
//        sum[i] -= a[pos];
//    }
//
//    cnt++;
//    sum[cnt] += a[pos];
//    dfs(pos+1);
//    sum[cnt] -= a[pos];
//    cnt--;
//    
//}
//bool cmp(int x ,int y)
//{
//    return x > y;
//}
//int main()
//{
//    cin >> n >> w;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i];
//    sort(a + 1, a + 1 + n,cmp);
//
//    dfs(1);
//    
//    cout << r << endl;
//    return 0;
//}


//#include<iostream>
//using namespace std;
//long long a, b, c;
//const int N = 1e5 + 10;
//long long f[21][21][21];
//long long w(long long aa,long long bb , long long cc)
//{
//    if (aa <= 0 || bb <= 0 || cc <= 0) return 1;
//    else if (aa > 20 || bb > 20 || cc > 20)
//    {
//        if (f[20][20][20] != 0) return f[20][20][20];
//        f[20][20][20] =  w(20, 20, 20);
//        return f[20][20][20];
//    }
//    else if (aa < bb && bb < cc)
//    {
//        if (f[aa][bb][cc] != 0) return f[aa][bb][cc];
//        f[aa][bb][cc] =  w(aa, bb, cc - 1) + w(aa, bb - 1, cc - 1) - w(aa, bb - 1, cc);
//        return f[aa][bb][cc];
//    }
//    else
//    {
//        if (f[aa][bb][cc] != 0) return f[aa][bb][cc];
//        f[aa][bb][cc] = w(aa - 1, bb, cc) + w(aa - 1, bb - 1, cc) + w(aa - 1, bb, cc - 1) - w(aa - 1, bb - 1, cc - 1);
//        return f[aa][bb][cc];
//    }
//}
//int main()
//{
//    while (cin >> a >> b >> c)
//    {
//        if (a == -1 && b == -1 && c == -1) break;
//        cout << 'w' << '(' << a << ", " << b << ", " << c << ')' << " = " << w(a, b, c) << endl;
//    }
//    return 0;
//}


//#include<iostream>
//#include<cstring>
//using namespace std;
//const int N = 1e4 + 10;
//char sx[N][N]; int t, p;
//
//int f(int x, int y)
//{
//    if (sx[x][y]) return sx[x][y];
//    sx[x][y] = '3';
//    
//    if (x == 0) return sx[x][y] = '1';
//    if (y == 0) return sx[x][y] = '2';
//    return sx[x][y] = f((x + y) % p, (x + y + y) % p);
//   
//}
//int main()
//{
//     cin >> t >> p;
//    int a, b;
//   
//    while (t--)
//    {
//        //多组测试数据不需要清空
//        cin >> a >> b;
//       char ret =  f(a , b);
//       if (ret == '3') cout << "error" << endl;
//       else cout << ret << endl;
//    }
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 110;
//int a[N][N]; int n,m;  int maxx = 1;
//int dx[4] = {1,-1,0,0};
//int dy[4] = {0,0,1,-1};
//int mp[N][N];
//int dfs(int x , int y)
//{
//    if (mp[x][y]) return mp[x][y];
//    int mmxx = 0;
//    for (int i = 0; i < 4; i++)
//    {
//        int xx = x + dx[i]; int yy = y + dy[i];
//        if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && a[x][y] > a[xx][yy])
//        {
//            mmxx = max(mmxx,dfs(xx,yy));
//        }
//    }
//    return mp[x][y] = mmxx+1;
//}
//int main()
//{
//    cin >> n >> m;
//    for(int i = 1 ; i <= n ; i++)
//        for (int j = 1; j <= m; j++)
//        {
//            cin >> a[i][j];
//        }
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//        {
//            maxx = max(dfs(i, j), maxx);
//        }
//    cout << maxx << endl;
//    return 0;
//}


//#include<iostream>
//#include<queue>
//using namespace std;
//int n, m, x, y;
//const int N = 410;
//int dx[8] = {1,2,-1,-2,-1,2,-2,1};
//int dy[8] = {2,1,-2,-1,2,-1,1,-2};
//bool st[N][N];
//int a[N][N]; queue<pair<int,int>> q;
//void bfs()
//{
//    q.push({ x,y }); st[x][y] = true; int h = 0; a[x][y] = h;
//    while (q.size())
//    {
//        int sz = q.size(); h++;
//        while (sz--)
//        {
//            int xx = q.front().first; int yy = q.front().second;
//            q.pop();
//            for (int i = 0; i < 8; i++)
//            {
//                int nx = xx + dx[i]; int ny = yy + dy[i];
//                if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !st[nx][ny])
//                {
//                    a[nx][ny] = h; q.push({nx,ny});
//                    st[nx][ny] = true;
//                }
//            }
//        }
//    }
//}
//int main()
//{
//    cin >> n >> m >> x >> y;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            a[i][j] = -1;
//        }
//     
//    }
//    bfs();
//
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            cout << a[i][j] << " ";
//        }
//        cout << endl;
//    }
//    return 0;
//}
//#include<iostream>
//#include<queue>
//using namespace std;
//const int N = 35;
//int n, m; 
//char a[N][N];
//int dx[4] = {0,0,1,-1};
//int dy[4] = {1,-1,0,0};
//bool st[N][N]; queue<pair<int, int>> q; 
//int ret;  int minn = N * N;
//void bfs(int x , int y)
//{
//    q.push({ x,y }); st[x][y] = true; int d = 0;
//    while (q.size())
//    {
//        int sz = q.size(); d++; 
//        while (sz--)
//        {
//            int xx = q.front().first; int yy = q.front().second; q.pop();
//            for (int i = 0; i < 4; i++)
//            {
//                int nx = xx + dx[i]; int ny = yy + dy[i]; 
//                if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !st[nx][ny] && a[nx][ny] != '*')
//                {
//                   
//                    if (a[nx][ny] == 'e')
//                    {
//                        ret++; minn = min(minn , d);   
//                    }
//                    else
//                    {
//                        q.push({nx , ny}); st[nx][ny] = true;
//                    }
//                }
//            }
//        }
//    }
//}
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            cin >> a[i][j];
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//        {
//            if(a[i][j] == 'k')
//            bfs(i,j);
//        }
//
//    if (ret)
//        cout << ret << " " << minn << endl;
//    else cout << -1 << endl;
//    return 0;
//}


//#include<iostream>
//#include<queue>
//using namespace std;
//const int N = 35;
//int n, m;
//char a[N][N];
//int dx[4] = { 0,0,1,-1 };
//int dy[4] = { 1,-1,0,0 };
//bool st[N][N]; queue<pair<int, int>> q;
//int ret;  int minn = N * N;  int x, y;
//void bfs()
//{
//
//    q.push({ x,y }); st[x][y] = true; int d = 0;
//    while (q.size())
//    {
//        int sz = q.size(); d++;
//        while (sz--)
//        {
//            int xx = q.front().first; int yy = q.front().second; q.pop();
//            for (int i = 0; i < 4; i++)
//            {
//                int nx = xx + dx[i]; int ny = yy + dy[i];
//                if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && !st[nx][ny] && a[nx][ny] != '*')
//                {
//
//                    if (a[nx][ny] == 'e')
//                    {
//                        ret++; minn = min(minn, d);
//                    }
//                    else
//                    {
//                        q.push({ nx , ny }); st[nx][ny] = true;
//                    }
//                }
//            }
//        }
//    }
//}
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            cin >> a[i][j];
//            if (a[i][j] == 'k')
//                x = i; y = j;
//        }
//    }
//    bfs();
//    if (ret)
//        cout << ret << " " << minn << endl;
//    else cout << -1 << endl;
//    return 0;
//}


//#include<iostream>
//#include<queue>
//#include<cstring>
//using namespace std;
//const int N = 1e5 + 10;
//int n = 1e5;
//int st[N];
//int t; int x, y; int ret;
//
//void dfs()
//{
//    queue<int> q;
//
//    st[x] = 0;
//    q.push(x); 
//    while (q.size())
//    {
//       
//            int xx = q.front(); q.pop();
//            int a = xx + 1;  int b = xx - 1; int c = xx * 2;
//            if (a <= n && st[a]== -1 )
//            {
//                q.push(a); st[a] = st[xx]+1;
//            }
//            if (b > 0 && st[b] == -1 )
//            {
//                q.push(b); st[b] = st[xx]+1;
//            }
//            if (c <= n && st[c] == -1)
//            {
//                q.push(c); st[c] = st[xx]+1;
//            }
//
//            if (a == y || b == y || c == y)
//            {
//                
//                return;
//            }
//        
//    }
//}
//int main()
//{
//    cin >> t;
//    while (t--)
//    {
//        memset(st,-1,sizeof st);
//        cin >> x >> y;
//        dfs();
//        cout << st[y] << endl;
//    }
//    return 0;
//}

//#include<iostream>
//#include<string>
//#include<queue>
//#include<unordered_map>
//using namespace std;
//int dx[4] = { 0,0,1,-1 };
//int dy[4] = {1,-1,0,0};
//  int ret;  string be;
//string s = "123804765";
//unordered_map<string, int> mp;
//void bfs()
//{
//    queue<string> q;
//    mp[be]++; q.push(be);
//    int h = 0;  
//    while (q.size())
//    {
//        int sz = q.size(); h++;
//        while (sz--)
//        {
//            string ss = q.front(); q.pop();
//            int num = ss.find('0') ;
//            int x = num / 3;  int y = num % 3;
//            for (int i = 0; i < 4; i++)
//            {
//                int xx = x + dx[i];  int yy = y + dy[i]; 
//                if (xx >= 0 && xx <= 2 && yy >= 0 && yy <= 2 )
//                {
//                    string sb = ss;  swap(sb[xx * 3 + yy], sb[num]);
//                    if (mp.count(sb)) continue;
//
//                    mp[sb]++;
//                    q.push(sb);
//                    if (sb == s)
//                    {
//                        ret = h;
//                        return;
//                    }
//                }
//            }
//        }
//    }
//}
//int main()
//{
//    cin >> be;
//    bfs();
//    cout << ret << endl;
//    return 0;
//}


//#include<iostream>
//#include<queue>
//using namespace std;
//const int N = 1e3 + 10;
//int dx[4] = { 0,0,1,-1 };
//int dy[4] = { 1,-1,0,0 };
//int n, m; 
//char a[N][N]; int b[N][N];  queue<pair<int, int>>q;
//bool st[N][N];
//void bfs()
//{
//    int h = 0;
//    while (q.size())
//    {
//        int sz = q.size(); h++;
//        while (sz--)
//        {
//            int x = q.front().first; int y = q.front().second; q.pop();
//            for (int i = 0; i < 4; i++)
//            {
//                int xx = x + dx[i]; int yy = y + dy[i];
//                if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && !st[xx][yy])
//                {
//                    st[xx][yy] = true;
//                    q.push({xx,yy});
//                    b[xx][yy] = h;
//                }
//            }
//        }
//    }
//
//}
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//        {
//            cin >> a[i][j];
//            if (a[i][j] == '1')
//            {
//                
//                q.push({ i,j });
//                st[i][j] = true;
//            }
//        }
//
//    bfs();
//
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            cout << b[i][j] << " ";
//        }
//        cout << endl;
//    }
//    return 0;
//}

//#include<iostream>
//#include<deque>
//#include<cstring>
//using namespace std;
//const int N = 510;
//int dx[4] = { 0,0,1,-1 };
//int dy[4] = { 1,-1,0,0 };
//char a[N][N]; int dist[N][N]; 
//int n, m;
//int curx1, cury1; 
//int x2, y2;
//void bfs()
//{
//    if (curx1 == x2 && cury1 == y2)
//    {
//        dist[x2][y2] = 0;
//        return;
//    }
//    deque<pair<int, int>> q;
//    memset(dist , -1 , sizeof dist);
//    q.push_back({ curx1,cury1 }); 
//    dist[curx1][cury1] = 0;
//    while (q.size())
//    {
//        int xx = q.front().first;  int yy = q.front().second; q.pop_front();
//        if (xx == x2 && yy == y2) return;
//        for (int i = 0; i < 4; i++)
//        {
//            int nx = xx + dx[i];  int ny = yy + dy[i];
//            if (nx >= 0 && nx < n && ny >= 0 && ny < m)
//            {
//                int w = (a[xx][yy] == a[nx][ny] ? 0 : 1);
//                if (dist[nx][ny] == -1)
//                {
//                    dist[nx][ny] = dist[xx][yy] + w;
//
//                    if (w == 0)
//                    {
//                        q.push_front({nx,ny});
//                    }
//                    else
//                    {
//                        q.push_back({nx,ny});
//                    }
//                }
//                else if (dist[xx][yy] + w < dist[nx][ny])
//                {
//                    dist[nx][ny] = dist[xx][yy] + w;
//
//                }
//            }
//        }
//    }
//}
//int main()
//{
//    while (1)
//    {
//        cin >> n >> m;
//        if (n == 0 && m == 0)break;
//        for (int i = 0; i < n; i++)
//            for (int j = 0; j < m; j++)
//                cin >> a[i][j];
//        cin >> curx1 >> cury1 >> x2 >> y2;
//        bfs();
//        cout << dist[x2][y2] << endl;
//    }
//    return 0;
//}


//#include<iostream>
//using namespace std;
//int n, m; char a[110][110];
//bool st[110][110];
//int ret;
//int dx[8] = { 0,0,1,-1 ,1,-1 ,1,-1};
//int dy[8] = { 1,-1,0,0 ,1,-1,-1, 1};
//void dfs(int x, int y)
//{
//    for (int i = 0; i < 8; i++)
//    {
//        int nx = x + dx[i]; 
//        int ny = y + dy[i];
//        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == 'W' && !st[nx][ny])
//        {
//            st[nx][ny] = true;
//            dfs(nx,ny);
//        }
//    }
//}
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            cin >> a[i][j];
//        }
//    }
//    for(int i = 1 ;i <= n ;i++)
//        for(int j = 1; j <= m ; j++)
//            if (a[i][j] == 'W' && !st[i][j])
//            {
//                ret++; dfs(i, j); st[i][j] = true;
//            }
//    cout << ret << endl;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 35;
//int a[N][N];  int n;
//bool st[N][N];
//int dx[4] = {0,0,1,-1};
//int dy[4] = {1,-1,0,0};
//void dfs(int x , int y)
//{
//    for (int i = 0; i < 4; i++)
//    {
//        int xx = x + dx[i];  int yy = y + dy[i];
//        if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && a[xx][yy] == 0 && !st[xx][yy])
//        {
//            st[xx][yy] = true;
//            dfs(xx, yy);
//        }
//    }
//}
//int main()
//{
//    cin >>n;
//    for (int i = 1 ;i <= n ;i++)
//    {
//        for (int j = 1; j <= n; j++)
//        {
//            cin >> a[i][j];
//        }
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        if (a[1][i] == 0 && !st[1][i]) { dfs(1, i);  st[1][i] = true; }
//        if (a[n][i] == 0 && !st[n][i]) { dfs(n, i); st[n][i] = true; }
//        if (a[i][1] == 0 && !st[i][1]) { dfs(i, 1); st[i][1] = true; }
//        if (a[i][n] == 0 && !st[i][n]) { dfs(i, n); st[i][n] = true; }
//    }
//
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= n; j++)
//        {
//            if (a[i][j] == 0 && !st[i][j])
//            {
//                a[i][j] = 2;
//            }
//            cout << a[i][j] << " ";
//
//        }
//        cout << endl; 
//    }
//
//
//   
//    return 0;
//}

//#include<iostream>
//#include<stack>
//using namespace std;
//const int N = 3e6 + 10;
//int a[N]; int n;  int b[N];
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i];
//    stack<int>st;
//    for (int i = n; i >= 1; i--)
//    {
//        while (st.size() && a[st.top()] <= a[i])st.pop();
//        if (st.size())
//            b[i] = st.top();
//
//        st.push(i);
//    }
//
//    for (int i = 1; i <= n; i++)
//        cout << b[i] << " ";
//    return 0; 
//}

//#include<iostream>
//#include<stack>
//using namespace std;
//const int N = 1e6 + 10;
//struct x
//{
//    int h;
//    int v;
//}a[N]; 
//int b[N];  
//int n;
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i].h >> a[i].v;
//    stack<int> s1, s2;
//    for (int i = 1; i <= n; i++)
//    {
//        while (s1.size() && a[s1.top()].h <= a[i].h) s1.pop();
//        if (s1.size())
//            b[s1.top()] += a[i].v;
//        s1.push(i);
//    }
//
//    for (int i = n; i >= 1; i--)
//    {
//        while (s2.size() && a[s2.top()].h <= a[i].h) s2.pop();
//        if (s2.size())
//            b[s2.top()] += a[i].v;
//        s2.push(i);
//    }
//    int ret = 0;
//    for (int i = 1; i <= n; i++)
//        ret = max(ret,b[i]);
//
//    cout << ret << endl;
//    return 0;
//}


//求的是每个数字左右的最远的比这个数大或者等于的值 正难则反
//求每个数字最靠近的且第一个比这个数字小的位置即可 so easy
//#include<iostream>
//#include<stack>
//#include<cstring>
//#include<cmath>
//using namespace std;
//long long n;
//const int N = 1e5 + 10;
//long long a[N];  long long b[N];  long long c[N];
//int main()
//{
//    while (1)
//    {
//        cin >> n;
//        if (n == 0) break;
//
//       
//        stack<int> s1, s2;
//        for (int i = 1; i <= n; i++)
//        {
//            cin >> a[i]; 
//        }
//        for (int i = 1; i <= n; i++)
//        {
//            while (s1.size() && a[s1.top()] >= a[i]) s1.pop();
//            if (s1.size())
//                b[i] = s1.top();
//            else b[i] = 0;
//            s1.push(i);
//        }
//        for (int i = n; i >= 1; i--)
//        {
//            while (s2.size() && a[s2.top()] >= a[i]) s2.pop();
//            if (s2.size())
//                c[i] = s2.top();
//            else c[i] = n + 1;
//            s2.push(i);
//        }
//
//        long long ret = 0; 
//        for (int i = 1; i <= n; i++)
//        {
//           long long d = c[i] - b[i] - 1;
//           
// 
//            
//            ret = max(ret, d * a[i]);
//
//        }
//        cout << ret << endl;
//    }
//    return 0;
//}


//#include<iostream>
//#include<deque>
//using namespace std;
//const int N = 1e6 + 10;
//int a[N];  int n, k;
//int main()
//{
//    cin >> n >> k;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i];
//    deque<int> q;
//
//    for (int i = 1; i <= n; i++)
//    {
//        while (q.size() && a[q.back()] >= a[i]) q.pop_back();
//        q.push_back(i);
//        if (q.back() - q.front() + 1 > k) q.pop_front();
//        if (i >= k) cout << a[q.front()] << " ";
//    }
//    cout << endl;
//    q.clear();
//    for (int i = 1; i <= n; i++)
//    {
//        while (q.size() && a[q.back()] <= a[i]) q.pop_back();
//
//        q.push_back(i);
//
//        if (q.back() - q.front() + 1 > k) q.pop_front();
//        if (i >= k) cout << a[q.front()] << " ";
//    }
//
//    return 0;
//}


//#include <iostream>
//#include <deque>
//using namespace std;
//const int N = 1e6 + 10;
//int n, k;
//int a[N];
//int main()
//{
//    cin >> n >> k;
//    for (int i = 1; i <= n; i++) cin >> a[i];
//    deque<int> q; // 存下标 
//    // 窗⼝内最⼩值 - 单调递增的队列 - 存下标 
//    for (int i = 1; i <= n; i++)
//    {
//        while (q.size() && a[q.back()] >= a[i]) q.pop_back();
//        q.push_back(i);
//        // 判断队列⾥⾯元素是否在合法窗⼝内 
//        if (q.back() - q.front() + 1 > k) q.pop_front();
//        if (i >= k) cout << a[q.front()] << " ";
//    }
//    cout << endl;
//    // 窗⼝内最⼤值 - 单调递减的队列 - 存下标 
//    q.clear();
//    for (int i = 1; i <= n; i++)
//    {
//        while (q.size() && a[q.back()] <= a[i]) q.pop_back();
//        q.push_back(i);
//        if (q.back() - q.front() + 1 > k) q.pop_front();
//        if (i >= k) cout << a[q.front()] << " ";
//    }
//    cout << endl;
//    return 0;
//}


//#include<iostream>
//using namespace std;
//#include<deque>
//const int N = 1e6 + 10;
//int a[N]; int n, k;
//int main()
//{
//    cin >> n >> k;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i];
//    deque<int> q;
//    for (int i = 1; i <= n; i++)
//    {
//        while (q.size() && a[q.back()] >= a[i]) q.pop_back();
//        q.push_back(i);
//
//        if (q.back() - q.front() + 1 > k) q.pop_front();
//        if (i >= k) cout << a[q.front()] << endl;
//    }
//    return 0;
//}


//#include<iostream>
//using namespace std;
//int n, m;  const int N = 1e6 + 10;
//int fa[N];
//int find(int x)
//{
//    if (fa[x] == x) return x;
//
//    return fa[x] = find(fa[x]);
//}
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++) fa[i] = i;
//    int a, b, c;
//    while (m--)
//    {
//        cin >> a >> b >> c;
//        if (a == 1)
//        {
//            fa[find(b)] = find(c);
//        }
//        else if (a == 2)
//        {
//            if (find(b) == find(c))
//                cout << 'Y' << endl;
//            else cout << 'N' << endl;
//        }
//    }
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 1e4 + 10;
//int fa[N]; int n, m, p;
//int find(int x)
//{
//    if (fa[x] == x) return x;
//
//    return fa[x] = find(fa[x]);
//}
//int main()
//{
//    cin >> n >> m >> p;
//    for (int i = 1; i <= n; i++)
//        fa[i] = i;  
//    int a, b;
//    while (m--)
//    {
//        cin >> a >> b;
//        fa[find(a)] = find(b);
//    }
//    while (p--)
//    {
//        cin >> a >> b;
//        if (find(a) == find(b)) cout << "Yes" << endl;
//        else cout << "No" << endl;
//    }
//    return 0;
//}

//#include<iostream>
//using namespace std;
//char a[111][111]; int n, m;  pair<int, int> fa[111][111];    int c[111][111];
//int dx[4] = { 0,1,1,1 };
//int dy[4] = { 1,0,1,-1 };
//pair<int, int> find(int x, int y)
//{
//    if (fa[x][y].first == x && fa[x][y].second == y) return fa[x][y];
//
//    return fa[x][y] = find(fa[x][y].first,fa[x][y].second);
//}
//int ret;
//int main() 
//{
//    cin >> n>> m;  
//    for (int i = 1; i <= n; i++)
//    {
//
//        for (int j = 1; j <= m; j++)
//        {
//            cin >> a[i][j];
//            if(a[i][j] == 'W')
//            fa[i][j] = { i,j };
//        }
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            if (a[i][j] == 'W')
//            {
//                for (int k = 0; k < 4; k++)
//                {
//                    int xx = i + dx[k];  int yy = j + dy[k];
//                    if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && a[xx][yy] == 'W')
//                    {
//                        auto r = find(i, j); 
//                        fa[r.first][r.second] = find(xx,yy);
//                    }
//                }
//            }
//        }
//    }
//
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            if (a[i][j] == 'W')
//            {
//                auto e = find(i, j);
//                if (c[e.first][e.second] == 0)
//                {
//                    ret++;
//                }
//                c[e.first][e.second]++;
//            }
//        }
//    }
//    cout << ret << endl;
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//char a[111][111]; int n, m;    int fa[N];   
//int dx[4] = { 0,1,1,1 };
//int dy[4] = { 1,0,1,-1 };  int ret;   int st[N];
//int find(int x ,int y)
//{
//    if (fa[x * m + y] == x * m + y)  return x * m + y;
//
//    return fa[x * m + y] = find(fa[x * m + y] / m, fa[x * m + y] % m);
//}
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//        {
//            cin >> a[i][j];
//            if (a[i][j] == 'W')
//                fa[i * m + j] = i * m + j;
//        }
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//        {
//            if(a[i][j] == 'W')
//            for (int k = 0; k < 4; k++)
//            {
//                int x = i + dx[k];  int y = j + dy[k];
//                if (x >= 1 && x <= n && y >= 1 && y <= m && a[x][j] == 'W')
//                {
//                    fa[find(i ,j)] = find(x , y); 
//                }
//            }
//        }
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//        {
//            if (a[i][j] == 'W')
//            {
//                if (st[find(i, j)] == 0)
//                {
//                    ret++;
//                }
//
//                st[find(i, j)]++;
//            }
//        }
//
//    cout << ret << endl;
//    return 0;
//}

//#include<iostream>
//#include<algorithm>
//#include<unordered_map>
//#include<cstring>
//using namespace std;
//const int N = 1e5+10;
//struct s
//{
//    int l1; int l2; int l3;
//}a[N];
// int t, n; int dist[N];  int pos;  int fa[N];  int cnt = 1;
//unordered_map<int, int> mp;
//void lisan() 
//{
//  
//    sort(dist + 1, dist + 1 + pos); 
//   
//    for (int i = 1; i <= pos; i++)
//    {
//       
//        if (mp.count(dist[i])) continue;
//        
//        mp[dist[i]] = cnt++;
//        mp[dist[i] + 1] = cnt++;
//    }
//}
//int find1(int x)
//{
//    if (fa[x] == x) return x;
//
//    return fa[x] = find1(fa[x]);
//}
//
//int main()
//{
//    cin >> t;
//    while (t--)
//    {
//        cin >> n;
//        memset(fa, 0, sizeof fa);
//        mp.clear();
//        cnt = 1;
//        pos = 0;
//
//        for (int i = 1; i <= n; i++)
//        {
//            cin >> a[i].l1 >> a[i].l2 >> a[i].l3;
//            dist[++pos] = a[i].l1;  dist[++pos] = a[i].l2;
//        }
//        lisan();
//
//        for (int i = 1; i <= cnt; i++)
//            fa[i] = i;
//
//        for (int i = 1; i <= n; i++)
//        {
//            if (a[i].l3 == 1)
//            {
//                fa[find1(mp[a[i].l1])] = find1(mp[a[i].l2]);
//            }
//           
//        }
//
//        int f = 0;
//        for (int i = 1; i <= n; i++)
//        {
//            if (a[i].l3 == 0)
//            {
//                if (find1(mp[a[i].l1]) == find1(mp[a[i].l2]))
//                {
//                    f = 1;
//                    break;
//                }
//            }
//        }
//        if (f)
//            cout << "NO" << endl;
//        else cout << "YES" << endl;
//    }
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 1e3 + 10;
//int fa[N * 2];  int n, m;
//int find(int x)
//{
//    if (fa[x] == x) return x;
//
//    return fa[x] = find(fa[x]);
//}
//int main()
//{
//    cin >> n >> m; 
//    char a; int b, c;
//    for (int i = 1; i <= n*2; i++)
//        fa[i] = i;
//
//    while (m--)
//    {
//        cin >> a >> b >> c;
//        if (a == 'E')
//        {
//            fa[find(c + n)] = find(b);//这里也是在统计朋友
//            fa[find(b + n)] = find(c);
//
//        }
//        else if (a == 'F')
//        {
//            fa[find(c)] = find(b);
//        }
//    }
//    int ret = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        if (fa[i] == i) ret++;
//    }
//    cout << ret << endl;
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 5e4 + 10;
//int fa[N*3];  int n, k;
//int find(int x)
//{
//    if (fa[x] == x) return x;
//    return fa[x] = find(fa[x]);
//}
//int main()
//{
//    cin >> n >> k;
//    for (int i = 1; i <= n * 3; i++)
//    {
//        fa[i] = i;
//    }
//    int a, b, c; int ret = 0;
//    while (k--)
//    {
//        cin >> a >> b >> c;
//        if (b > n || c > n)
//        {
//            ret++;
//            continue;
//        }
//
//        if (a == 1)//所有操作都是在找同类
//        {
//            if (find(b) == find(c+n) || find(b) == find(c+n+n))
//            {
//                ret++;
//                continue;
//            }
//
//            fa[find(b)] = find(c);
//            fa[find(b + n)] = find(c + n);
//            fa[find(b + 2*n)] = find(c + 2*n);
//        }
//        else if (a == 2)
//        {
//            if (b == c)
//            {
//                ret++; continue;
//            }
//
//            if (find(b) == find(c) || find(b) == find(c+n))
//            {
//                ret++;
//                continue;
//            }
//
//            fa[find(c + 2 * n)] = find(b);
//            fa[find(c + n)] = find(b + 2*n);
//            fa[find(b + n)] = find(c);
//        }
//    }
//    cout << ret << endl;
//    return 0;
//}


//#include<iostream>
//#include<string>
//#include<algorithm>
//using namespace std;
//const int N = 1e4 + 10;  
//unsigned long long ret;
//int pp = 131;  unsigned long long hh[N];
//int main()
//{
//    int r = 0;
//    int n; cin >> n;
//    string s;
//    for (int i = 1; i <= n; i++)
//    {
//        
//        ret = 0;
//        cin >> s;
//        for (int j = 0; j < s.size(); j++)
//        {
//            ret = ret * pp + s[j];
//        }
//
//        hh[i] = ret;
//    }
//    sort(hh + 1, hh + 1 + n);  unsigned long long prev = hh[1];
//    for (int i = 2; i <= n; i++)
//    {
//        if (hh[i] != prev)
//        {
//            r++;
//            prev = hh[i];
//        }
//    }
//    cout << r+1 << endl;
//    return 0;
//}


//#include<iostream>
//#include<string>
//using namespace std;
//typedef unsigned long long ull;
//const int N  = 1e6 + 10;
//ull f[N];  ull p[N];  int pp = 131;
//int main()
//{
//    string s; cin >> s;  s = " " + s;
//    int m = s.size();
//    p[0] = 1;
//    for (int i = 1; i <= m; i++)
//    {
//        p[i] = p[i - 1] * pp;
//        f[i] = f[i - 1] * pp + s[i];
//    }
//    int n;  cin >> n;  
//    while (n--)
//    {
//        int l1, l2, r1, r2;
//        cin >> l1 >> r1 >> l2 >> r2;
//        ull x1, x2;
//        x1 = f[r1] - f[l1-1] * p[r1 - l1 + 1];
//        x2 = f[r2] - f[l2-1] * p[r2 - l2 + 1];
//        if (x1 == x2)
//            cout << "Yes" << endl;
//        else
//            cout << "No" << endl;
//    }
//    return 0;
//}

//#include<iostream>
//#include<cstring>
//using namespace std;
//const int N = 3e6 + 10;
//int tree[N][62];   int p[N];
//int n, t, q;  int dex;
//int get_num(char x)
//{
//    if (x >= 'a' && x <= 'z')
//        return x - 'a';
//    else if (x >= 'A' && x <= 'Z') return x - 'A' + 26;
//    else if (x >= '0' && x <= '9') return x - '0' + 52;
//}
//void tree_init(string &s)
//{
//    int cur = 0; p[cur]++;
//    for (auto e : s)
//    {
//        int path = get_num(e);
//        if (tree[cur][path] == 0) tree[cur][path] = ++dex;
//        cur = tree[cur][path];
//        p[cur]++;
//    }
//}
//int tree_find(string &s)
//{
//    int cur = 0;
//    for (auto e : s)
//    {
//        int path = get_num(e);
//        if (tree[cur][path] == 0) return 0;
//        cur = tree[cur][path];
//    }
//    return p[cur];
//}
//int main()
//{
//    cin >> t;  string s;
//    while (t--)
//    {
//        for (int i = 0; i <= dex; i++)
//            p[i] = 0;
//        for (int i = 0; i <= dex; i++)
//            for (int j = 0; j < 62; j++)
//                tree[i][j] = 0;
//
//            
//        cin >> n >> q;   dex = 0;
//        for (int i = 1; i <= n; i++)
//        {
//            cin >> s;
//            tree_init(s);
//        }
//        for (int i = 1; i <= q; i++)
//        {
//            cin >> s;
//          cout <<  tree_find(s) <<endl;
//        }
//
//    }
//
//   
//    return 0;
//}


//#include<iostream>
//#include<cstring>
//using namespace std;
//const int N = 5e5+10; 
//int tr[N][26];  int e[N];  
//int n, q; int dex;
//void tr_insert(string& s)
//{
//    int cur = 0;
//    
//    for (auto e : s)
//    {
//        int path = e - 'a';
//        if (tr[cur][path] == 0) tr[cur][path] = ++dex;
//        cur = tr[cur][path]; 
//    }
//    e[cur]++;
//}
//int tr_find(string &s)
//{
//    int cur = 0;
//    for (auto e: s)
//    {
//        int path = e - 'a';
//        if (tr[cur][path] == 0) return 0;
//        cur = tr[cur][path];
//    }
//    if (e[cur] > 0)
//    {
//        int t = e[cur];
//        e[cur] = -1;
//        return t;
//    }
//    return e[cur];
//}
//int main()
//{
//    cin >> n; string s;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> s;
//        tr_insert(s);
//    }
//    cin >> q;
//    for (int i = 1; i <= q; i++)
//    {
//        cin >> s;
//        int x = tr_find(s);
//        if (x == 0)
//        {
//            cout << "WRONG" << endl;
//        }
//        else if (x > 0)
//        {
//            cout << "OK" << endl;
//        }
//        else cout << "REPEAT" << endl;
//    }
//
//    return 0;
//}

//
//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int a[N];  int n; int maxx; int num;  int sum;
//void dfs(int pos)
//{
//    if (sum == 2)
//    {
//        maxx = max(maxx, num);
//        return;
//    }
//    for (int i = pos; i <= n; i++)
//    {
//        num ^= a[i];  sum++;
//        dfs(i+1);
//        num ^= a[i]; sum--;
//    }
//}
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i];
//    dfs(1);
//    cout << maxx <<endl;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 60;
//int dp[N];
//int main()
//{
//    int n; cin >> n;
//    dp[0] = 0;  dp[1] = 1; dp[2] = 2; dp[3] = 4;
//    for (int i = 4; i <= n; i++)
//        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
//    cout << dp[n] << endl;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N =  1e3 + 10;
//int dp[N][N];
//int main()
//{
//    int r;  cin >> r;
//    for (int i = 1; i <= r; i++)
//    {
//        for (int j = 1; j <= i; j++)
//        {
//            cin >> dp[i][j];
//            if (j == 1) dp[i][j] += dp[i - 1][j];
//            else if (j == i) dp[i][j] += dp[i - 1][j - 1];
//            else
//            dp[i][j] += max(dp[i-1][j],dp[i-1][j-1]);
//        }
//    }
//    int ret = 0;
//    for (int i = 1; i <= r; i++)
//        ret = max(dp[r][i],ret);
//    cout << ret << endl;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int dp[N];
//int main()
//{
//    int n, k;
//    cin >> n >> k;
//    dp[0] = 1;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= k && i - j >= 0; j++)
//            dp[i] = (dp[i] % 100003 + dp[i-j] % 100003) % 100003;
//    }
//    cout << dp[n] << endl;
//    return 0;
//}
//#include<iostream>
//using namespace std;
//const int N = 2e5 + 10;
//long long dp[N];
//int main()
//{
//    int n; cin >> n;
//    for (int i = 1; i <= n; i++)
//    {
//        cin >> dp[i];
//    }
//    long long maxx = -1e16;
//    for (int i = 1; i <= n; i++)
//    {
//        dp[i] = max(dp[i], dp[i - 1] + dp[i]);
//        maxx = max(maxx , dp[i]);
//    }
//    cout << maxx << endl;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 35;
//int dp[N][N];
//int n, m;
//int main()
//{
//    cin >> n >> m;
//    dp[0][1] = 1;
//    for (int i = 1; i <= m; i++)
//    {
//        for (int j = 1; j <= n; j++)
//        {
//            if (j == 1)
//                dp[i][j] = dp[i - 1][j + 1] + dp[i - 1][m];
//            else if (j == m)
//                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][1];
//            else 
//                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
//        }
//    }
//    cout << dp[m][1] << endl;
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 360;  const int M = 50;
//int x[N]; int dp[M][M][M][M];  int cnt[5];
//int main()
//{
//    int n, m;  cin >> n >> m;
//    for (int i = 1; i <= n; i++)
//        cin >> x[i];
//    for (int i = 1; i <= m; i++)
//    {
//        int v; cin >> v; cnt[v]++;
//    }
//
//    dp[0][0][0][0] = x[1];
//    for(int i  = 0 ; i <= cnt[1] ;i++)
//        for(int j = 0 ; j <= cnt[2] ; j++)
//            for(int k = 0 ; k <= cnt[3] ; k++)
//                for (int l = 0; l <= cnt[4]; l++)
//                {
//                    int z =1+ i + 2 * j + 3 * k + 4 * l;
//                    int& t = dp[i][j][k][l];
//                    if (i) t = max(t, dp[i - 1][j][k][l] + x[z]);
//                    if (j) t = max(t, dp[i][j - 1][k][l] + x[z]);
//                    if (k) t = max(t, dp[i][j][k - 1][l] + x[z]);
//                    if (l) t = max(t, dp[i][j][k][l - 1] + x[z]);
//
//                }
//    cout << dp[cnt[1]][cnt[2]][cnt[3]][cnt[4]] << endl;
//    return 0;
//}



//#include <iostream>
//using namespace std;
//const int N = 360, M = 50;
//int n, m;
//int x[N], cnt[5];
//int f[M][M][M][M];
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++) cin >> x[i];
//    for (int i = 1; i <= m; i++)
//    {
//        int t; cin >> t;
//        cnt[t]++;
//    }
//    // 初始化 
//    f[0][0][0][0] = x[1];
//    for (int a = 0; a <= cnt[1]; a++)
//        for (int b = 0; b <= cnt[2]; b++)
//            for (int c = 0; c <= cnt[3]; c++)
//                for (int d = 0; d <= cnt[4]; d++)
//                {
//                    int i = 1 + a + 2 * b + 3 * c + 4 * d;
//                    int& t = f[a][b][c][d];
//                    if (a) t = max(t, f[a - 1][b][c][d] + x[i]);
//                    if (b) t = max(t, f[a][b - 1][c][d] + x[i]);
//                    if (c) t = max(t, f[a][b][c - 1][d] + x[i]);
//                    if (d) t = max(t, f[a][b][c][d - 1] + x[i]);
//                }
//    cout << f[cnt[1]][cnt[2]][cnt[3]][cnt[4]] << endl;
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 550;
//int a[N][N];  
//int main()
//{
//    int n, m; cin >> n >> m;
//    for (int i = 0; i <= n; i++)
//        for (int j = 0; j <= m; j++)
//            a[i][j] = 1e8;
//
//    a[0][1] = a[1][0] = 0;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//        {
//            cin >> a[i][j];
//            a[i][j] += min(a[i - 1][j], a[i][j - 1]);
//        }
//    cout << a[n][m] << endl;
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 3e3 + 10;
//int a[N][N];  int dp[N][N];
//int main()
//{
//    int  n, m; cin >> n >> m;
//
//    for(int i = 1; i <= n ; i++)
//        for (int j = 1; j <= m; j++)
//        {
//            cin >> a[i][j];
//        }
//    dp[n][0] = 1;
//    for(int i  =  n ; i >= 1 ; i--)
//        for (int j = 1; j <= m; j++)
//        {
//            if(a[i][j] == 0)
//            dp[i][j] = (dp[i][j - 1]%2333 + dp[i + 1][j]%2333)%2333;
//        }
//    cout << dp[1][m] << endl;
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 25;
//int dx[9] = {0, 1,2,-1,2,-2,1,-1,-2 };
//int dy[9] = {0, 2,1,2,-1,1,-2,-2,-1 };
//int dp[N][N];
//int a[N][N];
//int main()
//{
//    int n, m; cin >> n >> m; 
//    int x, y; cin >> x >> y;
//    n++; m++; x++; y++;
//    for (int i = 0; i <= 8; i++)
//    {
//        int xx = x + dx[i];
//        int yy = y + dy[i];
//        if (xx >= 1 && xx <= n && yy >= 1 && yy <= m)
//            a[xx][yy] = 1;
//    }
//    dp[1][0] = 1;
//    for(int i =1 ; i <= n  ;i++)
//        for (int j = 1; j <= m ; j++)
//        {
//            if (a[i][j] == 0)
//                dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
//        }
//    cout << dp[n][m] << endl;
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 5e3 + 10;
//int a[N];  int dp[N];
//int main()
//{
//    int n;  cin >> n;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i];
//    int ret = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        dp[i] = 1;
//        for (int j = 1; j < i; j++)
//        {
//            if (a[i] > a[j])
//                dp[i] =max( dp[i], dp[j] + 1);
//        }
//        ret = max(ret , dp[i]);
//    }
//    cout << ret << endl; 
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int a[N];
//int dp[N]; int len;
//int main()
//{
//    int n; cin >> n; 
//    for (int i = 1; i <= n; i++)
//        cin >> a[i];
//    for (int i = 1; i <= n; i++)
//    {
//        if (len == 0 || a[i] > dp[len])  dp[++len] = a[i];
//        int l = 1;  int r = len;
//        while (r > l)
//        {
//            int mid = l + (r - l) / 2;
//            if (dp[mid] >= a[i]) r = mid;
//            else l = mid + 1;
//        }
//        dp[l] = a[i];
//    }
//    cout << len << endl;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 110;
//int a[N];
//int f[N];
//int d[N];
//int main()
//{
//    int n; cin >> n;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i];
//    for (int i = 1; i <= n; i++)
//    {
//        f[i] = d[i] = 1;
//        for (int j = 1; j < i; j++)
//        {
//            if (a[i] > a[j])
//                f[i] = max(f[i], f[j] + 1);
//            else if (a[i] < a[j])
//                d[i] = max(d[i],d[j]+1);
//            else
//
//        }
//    }
//    int ret = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        ret = max(ret, f[i] + d[i] - 1);
//    }
//    cout <<n- ret << endl;
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 110;
//int a[N];
//int f[N];
//int d[N];
//int main()
//{
//    int n; cin >> n;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i];
//    for (int i = 1; i <= n; i++)
//    {
//        f[i] = 1;
//        for (int j = 1; j < i; j++)
//        {
//            if (a[i] > a[j])
//                f[i] = max(f[i], f[j] + 1);
//        }
//    }
//
//    for (int i = n; i >= 1; i--)
//    {
//         d[i] = 1;
//        for (int j = n; j > i; j--)
//        {
//            if (a[i] > a[j])
//                d[i] = max(d[i], d[j] + 1);
//        }
//    }
//    int ret = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        ret = max(ret, f[i] + d[i] - 1);
//    }
//    cout << n - ret << endl;
//    return 0;
//}


//#include<iostream>
//#include<cstring>
//using namespace std;
//string s1, s2;
//const int N = 5e3 + 10;
//int dp[N][N];
//int main()
//{
//    while (cin >> s1 >> s2)
//    {
//        s1 = " " + s1;
//        s2 = " " + s2;
//        int n = s1.size();
//        int m = s2.size();
//        
//       
//        for (int i = 1; i < n; i++)
//        {
//            for (int j = 1; j < m; j++)
//            {
//                if (s1[i] == s2[j])
//                {
//                    dp[i][j] = dp[i - 1][j - 1] + 1;
//                }
//                else
//                {
//                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
//                }
//
//            }
//
//        }
//        cout << dp[n-1][m-1] << endl;
//    }
//    return 0;
//}


//#include <iostream>
//using namespace std;
//const int N = 5010;
//string s, t;
//int f[N][N];
//int main()
//{
//    while (cin >> s >> t)
//    {
//        int n = s.size(), m = t.size();
//        // s = " " + s, t = " " + t;
//
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 1; j <= m; j++)
//            {
//                if (s[i - 1] == t[j - 1]) f[i][j] = f[i - 1][j - 1] + 1;
//                else f[i][j] = max(f[i - 1][j], f[i][j - 1]);
//            }
//        }
//
//        cout << f[n][m] << endl;
//    }
//
//    return 0;
//}


//#include<iostream>
//#include<cstring>
//using namespace std;
//string s1, s2;
//const int N = 2e3 + 10;
//int dp[N][N];
//int main()
//{
//    cin >> s1 >> s2;
//    
//        int n = s1.size();
//        int m = s2.size();
//        int maxx = max(n,m);
//        s1 = " " + s1;
//        s2 = " " + s2;
//        for (int i = 1; i <= n; i++)
//        {
//            for (int j = 1; j <= m; j++)
//            {
//                if (s1[i] == s2[j])
//                {
//                    dp[i][j] = dp[i - 1][j - 1] + 1;
//                }
//                else
//                {
//                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
//                }
//
//            }
//
//        }
//
//        cout <<maxx- dp[n][m] << endl;
//    
//    return 0;
//}



//#include<iostream>
//#include<cstring>
//using namespace std;
//const int N = 2e3 + 10;
//int dp[N][N];
//string s, t;
//int main()
//{
//    cin >> s >> t;
//    int n = s.size();  int m = t.size();
//    s = " " + s; t = " " + t;
//
//    for (int i = 1; i <= n; i++)
//        dp[i][0] = i;
//    for (int i = 1; i <= m; i++)
//        dp[0][i] = i;
//
//    for(int i = 1 ; i <= n ; i++)
//        for (int j = 1; j <= m; j++)
//        {
//            if (s[i] == t[j])
//            {
//                dp[i][j] = dp[i-1][j-1];
//            }
//            else
//            {
//                dp[i][j] = min(dp[i][j-1],min(dp[i-1][j-1],dp[i-1][j])) + 1;
//            }
//        }
//    cout << dp[n][m] << endl;
//    return 0;
//}

//#include<iostream>
//#include<string>
//using namespace std;
//const int N = 1e3 + 10;
//int a[N][N];
//int main()
//{
//    string s;
//    cin >> s;
//    int n = s.size();
//    s = " " + s;
//    for(int len = 2 ; len <= n ;len++ )//len等于1 或者2 都可以 当等于1时 一个字符自己就是一个回文字符串
//        for (int i = 1; i + len - 1 <= n; i++)
//        {
//            int j = i + len - 1;
//            if (s[i] == s[j])
//                a[i][j] = a[i + 1][j - 1];
//            else
//                a[i][j] = min(a[i+1][j],a[i][j-1])+1;
//
//        }
//    cout << a[1][n] << endl;
//    return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 2e3 + 10;
//int dp[N][N];
//int a[N];
//int main()
//{
//    int n; cin >> n;
//    for (int i = 1; i <= n; i++)
//        cin >> a[i];
//    for(int len = 1; len <= n ;len++)
//        for (int i = 1; i + len - 1 <= n; i++)
//        {
//            int j = i + len - 1;
//            int cnt = n - len + 1;
//            dp[i][j] = max(a[i]*cnt+dp[i+1][j], a[j]*cnt+dp[i][j-1]);
//        }
//    cout << dp[1][n] << endl;
//    return 0;
//}

//#include<iostream>
//#include<cstring>
//#include<queue>
//using namespace std;
//const int N = 1010;
//int n, m;
//int edges[N][N];
//bool st[N];
//void dfs(int u)
//{
//    cout << u << endl;
//    st[u] = true;
//
//    for (int v = 1; v <= n; v++)
//    {
//        if (edges[u][v] != -1 && !st[v])
//            dfs(v);
//    }
//}
//
//void bfs(int u)
//{
//    queue<int> q;
//    cout << u << endl;  q.push(u); st[u] = true;
//    while (q.size())
//    {
//        u = q.front();  q.pop();
//        for (int i = 1; i <= n; i++)
//        {
//            
//            if (!st[i] && edges[u][i] != -1)
//            {
//                q.push(i); st[i] = true;
//                cout << i << endl;
//            }
//        }
//    }
//}
//
//int main()
//{
//    memset(edges , -1 , sizeof edges);
//    cin >> n >> m;
//    for(int i = 1 ;  i <= m ; i++)
//    {
//        int a, b, c; cin >> a >> b >> c;
//        edges[a][b] = c;
//        edges[b][a] = c;  //这里是无向图需要存一下
//    }
//
//    
//    return 0;
//}

//#include<iostream>
//#include<vector>
//using namespace std;
//typedef pair<int, int> pll;
//const int N = 1e5 + 10;
//int n, m;
//vector<pll> edges[N];
//bool st[N];
//void dfs(int u)
//{
//    cout << u << endl;
//    st[u] = true;
//
//    for (auto& e : edges[u])
//    {
//        int v = e.first;  int w = e.second;
//        if (!st[v])
//            dfs(v);
//    }
//}
//
//void bfs(int u)
//{
//    queue<int> q; q.push(u); st[u] = true;
//
//    while (q.size())
//    {
//        int uu = q.front(); q.pop();
//        cout << uu << endl;
//        for (auto e : edges[uu])
//        {
//            int v = e.first;
//            if (!st[v])
//            {
//                q.push(v); st[v] = true;
//            }
//        }
//    }
//
//}
//
//int main()
//{
//    
//    cin >> n >> m;
//    for (int i = 1; i <= m; i++)
//    {
//        int a, b, c; cin >> a >> b >> c;
//        edges[a].push_back({ b,c });
//        edges[b].push_back({a,c});//无向图需要反向存一下
//    }
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//
//int h[N], e[N * 2], ne[N * 2], w[N * 2], id;
//int n, m;
//void add(int a,int b, int c)
//{
//    id++;
//    e[id] = b;
//    w[id] = c;
//    ne[id] = h[a];
//    h[a] = id;
//}
//
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= m; i++)
//    {
//        int a, b, c; cin >> a >> b >> c;
//        add(a, b, c); add(b,a,c);
//    }
//    return 0;
//}



//#include<iostream>
//#include<cstring>
//using namespace std;
//const int N = 5010 , INF = 0x3f3f3f3f;
//int n, m;
//int edges[N][N];
//int dist[N];
//bool st[N];
//int prim()
//{
//    memset(dist , 0x3f , sizeof dist);
//    dist[1] = 0;
//    int ret = 0;
//    for (int i = 1; i<= n ; i++)
//    {
//        int t = 0;
//        for (int j = 1; j <= n; j++)
//            if (!st[j] && dist[j] < dist[t])
//                t = j;
//        if (dist[t] == INF) return INF;
//        st[t] = true;
//        ret += dist[t];
//
//        for (int j = 1; j <= n; j++)
//            dist[j] = min(dist[j] , edges[i][j]);
//    }
//    return ret;
//}
//int main()
//{
//    cin >> n >> m;
//    memset(edges , 0x3f , sizeof edges);
//    for (int i = 1; i <= m; i++)
//    {
//        int a, b, c; cin >> a >> b >> c;
//        edges[a][b] = edges[b][a] = min(edges[a][b],c);
//    }
//
//    int ret = prim();
//    if (ret == INF) cout << "orz" << endl;
//    else cout << ret << endl;
//    return 0;
//}


//#include<iostream>
//#include<vector>
//#include<cstring>
//using namespace std;
//const int N = 5010 , INF = 0x3f3f3f3f;
//typedef pair<int, int> pll;
//vector<pll> edges[N];
//int dist[N];
//bool st[N];
//int n, m;
//
//int prim()
//{
//    memset(dist , 0x3f , sizeof dist);
//    dist[1] = 0;
//    int ret = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        int t = 0;
//        for (int j = 1; j <= n; j++)
//            if (!st[j] && dist[j] < dist[t])
//                t = j;
//        if (dist[t] == INF) return INF;
//        st[t] = true;
//        ret += dist[t];
//
//        for (auto& e : edges[t])
//        {
//            int v = e.first;  int w = e.second;
//            dist[v] = min(dist[v], w);
//        }
//    }
//    return ret;
//}
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= m; i++)
//    {
//        int x, y, z; cin >> x >> y >> z;
//        edges[x].push_back({ y,z });
//        edges[y].push_back({ x,z });
//    }
//    int ret = prim();
//    if (ret == INF) cout << "orz" << endl;
//    else cout << ret << endl;
//    return 0;
//}


//#include<iostream>
//#include<cstring>
//using namespace std;
//int n, m;
//const int N = 5e3 + 10 , INF = 0x3f3f3f3f;
//int e[N][N];
//bool st[N];
//int dist[N];
//int prim()
//{
//    int ret = 0;
//    memset(dist, 0x3f, sizeof dist);//这里是对每一字节位进行填充 不是直接对一个类型变量赋值
//    dist[1] = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        int t = 0;
//        for (int j = 1; j <= n; j++)
//            if (!st[j] && dist[j] < dist[t]) t = j;
//
//        if (dist[t] == INF) return INF;
//        ret += dist[t];
//        st[t] = true;
//        for (int j = 1; j <= n; j++)
//        {
//            dist[j] = min(dist[j],e[t][j]);
//        }
//     }
//    return ret;
//}
//int main()
//{
//    memset(e,0x3f,sizeof e);
//    cin >> n >> m;
//    for (int i = 1; i <= m; i++)
//    {
//        int a, b, c;
//        cin >> a >> b >> c;
//        e[a][b] = e[b][a] = min(c,e[a][b]);
//        
//    }
//    int ret = prim();
//    if (ret == INF) cout << "orz" << endl;
//    else cout << ret << endl;
//    return 0;
//}


//#include<iostream>
//#include<cstring>
//using namespace std;
//int n, m;
//const int N = 5e3 + 10,INF = 0x3f3f3f3f;
//bool st[N];
//int e[N][N];
//int dist[N];
//int prim()
//{
//    int ret = n;
//    memset(dist , 0x3f , sizeof dist);
//    dist[1] = 0;
//    for (int i = 1; i <= m; i++)
//    {
//        int t = 0;
//        for (int j = 1; j <= m; j++)
//            if (!st[j] && dist[j] < dist[t]) t = j;
//        if (dist[t] == INF) ret += n;
//        else ret += dist[t];
//        st[t] = true;
//        for (int j = 1; j <= m; j++)
//        {
//            dist[j] = min(dist[j] , e[t][j]);
//        }
//    }
//    return ret;
//}
//int main()
//{
//    memset(e,0x3f , sizeof e);
//    cin >> n >> m;
//    for (int i = 1; i <= m; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            int c; cin >> c;  if (c == 0 || c >= n) continue;
//            e[i][j]  = min(c, e[i][j]);
//        }
//    }
//
//    int ret = prim();
//    cout << ret << endl;
//    return 0;
//}


//#include<iostream>
//#include<cstring>
//using namespace std;
//const int N = 3e2 + 10, INF = 0x3f3f3f3f;
//int n, m;   int maxx = 0;
//int dist[N];
//int e[N][N];
//bool st[N];
//int prim()
//{
//    int ret = -1; 
//    memset(dist ,0x3f, sizeof dist);
//    dist[1] = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        int t = 0; 
//        for (int j = 1; j <= n; j++)
//            if (!st[j] && dist[j] < dist[t]) t = j;
//        ret++;
//        st[t] = true;
//        maxx = max(maxx , dist[t]);
//        for (int j = 1; j <= n; j++)
//            dist[j] = min(dist[j],e[t][j]);
//    }
//    return ret;
//}
//int main()
//{
//    memset(e,0x3f,sizeof e);
//    cin >> n >> m;
//    for (int i = 1; i <= m; i++)
//    {
//        int x, y, z;
//        cin >> x >> y >> z;
//        e[x][y] = e[y][x] = z;
//    }
//    int ret = prim();
//    cout << ret << " "<< maxx << endl;
//    return 0;
//}


//#include<iostream>
//#include<cstring>
//#include<vector>
//using namespace std;
//const int N = 1e5 + 10, INF = 0x3f3f3f3f;
//int n, m; 
//int dist[N];
//typedef pair<int, int> pll;
//vector<pll> e[N];
//int a[N];  int maxx = 0;
//bool st[N];
//int prim()
//{
//    int ret = 0;
//    memset(dist , 0x3f , sizeof dist);
//    dist[1] = 0;
//    for (int i = 1; i <= n; i++)
//    {
//        int t = 0;
//        for (int j = 1; j <= n; j++)
//            if (!st[j] && dist[j] < dist[t]) t = j;
//        if (dist[t] == INF) break;
//        maxx += dist[t];
//        st[t] = true;
//        ret++;
//        for (auto h : e[t])
//        {
//            int y = h.first;  int z = h.second;
//            dist[y] = min(dist[y], z);
//        }
//    }
//    return ret;
//}
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++) cin >> a[i];
//    for (int i = 1 ;i <= m; i++)
//    {
//        int x, y, z;
//        cin >> x >> y >> z;
//        if (a[x] > a[y]) e[x].push_back({ y,z });
//        else e[y].push_back({x,z});
//    }
//    int ret = prim();
//    cout << ret << " " << maxx << endl;
//    return 0;
//}

//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 5e3 + 10 , INF = 0x3f3f3f3f , M = 2e5+10;
//int n, m;
//int fa[N];
//struct node
//{
//    int x, y, z;
//}a[M];
//bool cmp(node& x , node& y)
//{
//    return x.z < y.z;
//}
//int find(int x )
//{
//    return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
//}
//int kk()
//{
//    sort(a+1 ,a+m+1 , cmp );
//    int cnt = 0;
//    int ret = 0;
//    for (int i = 1; i <= m; i++)
//    {
//        int x = a[i].x; int y = a[i].y; int z = a[i].z;
//        int fx = find(x);  int fy = find(y);
//        if (fx != fy)
//        {
//            cnt++;
//            ret += z;
//            fa[fx] = fy;
//        }
//    }
//    return cnt == n - 1 ? ret : INF;
//}
//
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= m; i++)
//    {
//        cin >>a[i]. x >> a[i].y >> a[i].z;
//    }
//    for (int i = 1; i <= n; i++)
//        fa[i] = i;
//    int ret = kk();
//    if (ret == INF) cout << "orz" << endl;
//    else cout << ret << endl;
//    return 0;
//}
//
//


//#include<iostream>
//#include<algorithm>
//#include<vector>
//using namespace std;
//const int N = 1e5+10 , M = 1e6+10;
//typedef long long ll;
//int n, m; 
//ll cnt;  int pos;
//typedef pair<int, int> pll;
//int fa[N];  ll ret;
//struct node
//{
//    int x,  y,  z;
//}a[M];
//int h[N];
//vector<pll>edge[M];
//bool st[N];
//void dfs(int u)
//{
//    cnt++;
//    st[u] = true;
//    for (auto & e : edge[u])
//    {
//        int v = e.first;  int c = e.second;
//        pos++;
//        a[pos].x = u; a[pos].y = v; a[pos].z = c;
//        if (!st[v]) dfs(v);
//    }
//}
//int find(int x)
//{
//    return x == fa[x] ? fa[x] : fa[x] = find(fa[x]);
//}
//bool cmp(node & a ,node & b)
//{
//    int y1 = a.y; int z1 = a.z;  int y2 = b.y; int z2 = b.z;
//    if (h[y1] != h[y2]) return h[y1] > h[y2];
//    else return z1 < z2;
//}
//void kk()
//{
//    for (int i = 1; i <= n; i++)
//        fa[i] = i;
//    
//    sort(a+1 , a+1+m , cmp);
//    for (int i = 1; i <= m; i++)
//    {
//        int x = a[i].x;  int y = a[i].y;  int z = a[i].z;
//        int fx = find(x);  int fy = find(y);
//        if (fx != fy)
//        {
//            ret += z;
//            fa[fx] = fy;
//        }
//    }
//    
//}
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++) cin >> h[i];
//    for (int i = 1; i <= m; i++)
//    {
//        int x, y, z; cin >> x >> y >> z;
//        if (h[x] >= h[y]) edge[x].push_back({y,z});
//        if (h[x] <= h[y]) edge[y].push_back({x,z});
//    }
//    dfs(1);
//    cout << cnt << " ";
//    kk();
//    cout << ret << endl;
//
//    return 0;
//}


//#include<iostream>
//#include<queue>
//#include<vector>
//using namespace std;
//const int N = 110;
//int n;
//vector<int>e[N];
//int in[N];
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++)
//    {
//        int j = 0;
//        while (cin >> j)
//        {
//            if (j == 0) break;
//            e[i].push_back(j);
//            in[j]++;
//        }
//    }
//
//    queue<int> q;
//    for (int i = 1; i <= n; i++)
//    {
//        if (in[i] == 0)
//            q.push(i);
//    }
//
//    while (q.size())
//    {
//        int x = q.front(); q.pop();
//        cout << x << " ";
//        for (auto h : e[x])
//        {
//            in[h]--;
//            if (in[h] == 0)
//                q.push(h);
//        }
//    }
//    return 0;
//}

//#include<iostream>
//#include<queue>
//#include<vector>
//using namespace std;
//const int N = 510;
//vector<int>e[N];
//int in[N];  int n;
//bool hh[510];
//int main()
//{
//    cin >> n; 
//    for (int i = 1; i <= n; i++)
//    {
//        int x, y;
//        cin >> x >> y;
//        hh[x] = true;
//        for (int i = 1; i <= y; i++)
//        {
//            int z; cin >> z;
//            e[x].push_back(z);
//            in[z]++;
//        }
//
//    }
//
//    queue<int> q;
//    for (int i = 0; i <= 500; i++)
//        if (in[i] == 0 && hh[i]) q.push(i);
//    while (q.size())
//    {
//        int x = q.front(); q.pop();
//        n--;
//        for (auto h : e[x])
//        {
//            in[h]--;
//            if (in[h] == 0 && hh[h])
//            {
//                q.push(h);
//            }
//        }
//    }
//    if (n <= 0) cout << "YES" << endl;
//    else cout << n << endl;
//    return 0;
//}


//#include<iostream>
//#include<queue>
//#include<vector>
//using namespace std;
//const int N = 5e3 + 10 , M = 80112002;
//int n, m;
//vector<int> e[N];
//int in[N];
//bool st[N];
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= m; i++)
//    {
//        int x, y;  cin >> x >> y; 
//        st[x] = st[y] = true;
//        e[y].push_back(x);
//        in[x]++;
//    }
//    queue<int> q;
//    for (int i = 0; i <= 5000; i++)
//    {
//        if (in[i] == 0 && st[i]) q.push(i);
//    }
//    int ret = 0;
//    while (q.size())
//    {
//        int x = q.front(); q.pop();
//        ret = (ret%M+1)%M;
//        for (auto h : e[x])
//        {
//            in[h]--;
//            if (in[h] == 0 && st[h])
//            {
//                q.push(h);
//            }
//        }
//
//    }
//    cout << ret % M << endl;
//    return 0;
//}


//#include<iostream>
//#include<vector>
//#include<queue>
//using namespace std;
//const int N = 5e3 + 10, MOD = 80112002;
//int m, n;
//int f[N];
//vector<int> e[N];
//int in[N], out[N];
//queue<int> q;
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= m; i++)
//    {
//        int x, y; cin >> x >> y;
//        in[y]++;  out[x]++;
//        e[x].push_back(y);
//    }
//
//    int ret = 0;
//    for (int i = 1; i <= n; i++)
//        if (in[i] == 0)
//        {
//            f[i] = 1;
//            q.push(i);
//        }
//    while (q.size())
//    {
//        int x = q.front();  q.pop();
//        for (auto y : e[x])
//        {
//            f[y] = (f[y] + f[x]) % MOD;
//            in[y]--;
//            if (in[y] == 0)
//            {
//                q.push(y);
//            }
//        }
//    }
//
//    for (int i = 1; i <= n; i++)
//    {
//        if (out[i] == 0)
//            ret = (ret + f[i]) % MOD;
//    }
//    cout << ret % MOD << endl;
//    return 0;
//}


//#include<iostream>
//#include<queue>
//#include<vector>
//using namespace std;
//const int N = 1e4 + 10;
//int in[N];
//vector<int>e[N];
//int ret;
//int len[N];
//int f[N]; int n;
//int main()
//{
//    cin >> n ;
//    for (int i =1 ; i <= n ; i++)
//    {
//        int  x;  cin >> x >> len[x]; int y;
//        while (cin >> y)
//        {
//            if (y == 0) break;
//            e[x].push_back(y);
//            in[y]++;
//        }
//    }
//    queue<int> q;
//    for(int i = 1 ; i <= n ; i++)
//    {
//        if (in[i] == 0)
//            q.push(i);
//    }
//    while (q.size())
//    {
//        int x = q.front();  q.pop();
//        f[x] += len[x];
//        ret = max(ret, f[x]);
//        for (auto y : e[x])
//        {
//            in[y]--;
//            f[y] = max(f[y],f[x]);
//            if (in[y] == 0)
//                q.push(y);
//        }
//    }
//    cout << ret << endl;
//    return 0;
//}


//#include<iostream>
//#include<queue>
//#include<cmath>
//#include<vector>
//using namespace std;
//const int N = 1e4 + 10 , INF = 2147483647;
//typedef pair<int, int> pll;
//typedef long long LL;
//vector<pll> e[N];
//LL dist[N];
//bool st[N];
//int n, m , s;
//void dj()
//{
//    for (int i = 0; i <= n; i++)
//        dist[i] = INF;
//    dist[s] = 0;
//    for (int i = 1; i < n; i++)
//    {
//        int u = 0;
//        for (int j = 1; j <= n; j++)
//        {
//            if (dist[j] < dist[u] && !st[j]) u = j;
//        }
//        st[u] = true;
//        for (auto v : e[u])
//        {
//            int vv = v.first;  int z = v.second;
//            if (dist[u] + z < dist[vv])
//                dist[vv] = dist[u] + z;
//        }
//
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        cout << dist[i] << " ";
//    }
//}
//int main()
//{
//    cin >> n >> m >> s;
//    for (int i = 1; i <= m; i++)
//    {
//        int x, y, z; cin >> x >> y >> z;
//        e[x].push_back({y,z});
//    }
//    dj();
//    
//    
//    return 0;
//}
//#include<iostream>
//#include<queue>
//#include<vector>
//#include<cstring>
//using namespace std;
//const int N = 1e5 + 10, INF = 2147483647;
//typedef pair<int, int> pll;
//vector<pll> e[N];  int n, m,s;
//int dist[N];
//bool st[N];
//
//void dj()
//{
//    priority_queue<pll, vector<pll>, greater<pll>> q;
//    memset(dist , 0x3f , sizeof dist);
//         dist[s] = 0;
//        q.push({ 0, s });
//        while (q.size())
//        {
//            int u = q.top().second;    q.pop();
//            if (st[u])  continue;
//            st[u] = true;
//            for (auto v : e[u])
//            {
//                int y = v.first;  int z = v.second;
//                
//                if (dist[u] + z < dist[y])
//                {
//                    dist[y] = dist[u] + z;
//                    q.push({dist[y],y});
//                }
//            }
//        }
//    
//        for (int i = 1; i <= n; i++)
//            cout << dist[i] << " ";
//}
//int main()
//{
//    cin >> n >> m >> s;
//    for (int i = 1; i <= m; i++)
//    {
//        int x, y, w;
//        cin >> x >> y >> w;
//        e[x].push_back({y,w});
//    }
//    dj();
//    return 0;
//}

//#include<iostream>
//#include<vector>
//using namespace std;
//const int N = 1e5 + 10 , INF = 2147483647;
//typedef pair<int, int> pll;
//vector<pll> e[N];
//int n, m, s;
//int dist[N];
//void bf()
//{
//    for (int i = 0; i <= n; i++)
//        dist[i] = INF;
//    dist[s] = 0;
//    bool flag = false;
//    for (int i = 1; i < n; i++)
//    {  
//        flag = false;
//        for (int j = 1; j <= n; j++)
//        {
//            if (dist[j] == INF) continue;
//            for (auto h : e[j])
//            {
//                int y = h.first;  int z = h.second;
//                if (dist[j] + z < dist[y])
//                {
//                    flag = true;
//                    dist[y] = dist[j] + z;
//                }
//            }
//        }
//        if (!flag) break;
//    }
//
//    for (int i = 1; i <= n; i++)
//    {
//        cout << dist[i] << " ";
//    }
//}
//int main()
//{
//    cin >> n >> m >> s;
//    for (int i = 1; i <= m; i++)
//    {
//        int x, y, z;  cin >> x >> y >> z;
//        e[x].push_back({ y,z });
//    }
//    bf();
//    return 0;
//}


//#include<iostream>
//#include<queue>
//#include<vector>
//using namespace std;
//int n, m, s; 
//typedef pair<int, int > pll;
//const int N = 1e4+10 , INF = 2147483647;
//vector<pll> e[N];
//int dist[N];
//bool st[N];
//void spaf()
//{
//    for (int i = 0; i <= n; i++) dist[i] = INF;
//    dist[s] = 0;
//    queue<int> q;
//    q.push(s);
//    st[s] = true;
//    while (q.size())
//    {
//        auto a = q.front();  q.pop();
//        st[a] = false;
//        for (auto h : e[a])
//        {
//            int y = h.first;  int z = h.second;
//            if (dist[a] + z < dist[y])
//            {
//                dist[y] = dist[a] + z;
//                if (!st[y])
//                {
//                    st[y] = true;
//                    q.push(y);
//                }
//            }
//        }
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        cout << dist[i] << " "; 
//    }
//}
//int main()
//{
//    cin >> n >> m >> s;
//    for (int i = 1; i <= m; i++)
//    {
//        int x, y, z; cin >> x >> y >> z;
//        e[x].push_back({y,z});
//    }
//    spaf();
//    return 0;
//}


//#include<iostream>
//#include<queue>
//#include<vector>
//#include<cstring>
//using namespace std;
//const int N = 1e5 + 10;
//typedef pair<int, int> pll;
//int dist[N];
//bool st[N];
//vector<pll>e[N];
//int n, m, s;
//void dj()
//{
//    priority_queue<pll, vector<pll>, greater<pll>> q;
//    memset(dist , 0x3f , sizeof dist);
//    dist[s] = 0;
//    q.push({0,s});
//    while (q.size())
//    {
//        int u = q.top().second;   q.pop();
//        if (st[u]) continue;
//        st[u] = true;
//        for (auto h : e[u])
//        {
//            int y = h.first; int z = h.second;
//            if (dist[u] + z < dist[y])
//            {
//                dist[y] = dist[u] + z;
//                q.push({dist[y],y});
//            }
//        }
//    }
//
//    for (int i = 1; i <= n; i++)
//        cout << dist[i] << " ";
//}
//int main()
//{
//    cin >> n >> m >> s;
//    for (int i = 1; i <= m; i++)
//    {
//        int x, y, z; cin >> x >> y >> z;
//        e[x].push_back({y,z});
//    }
//
//    dj();
//    return 0;
//}


//#include<iostream>
//#include<vector>
//#include<cstring>
//#include<queue>
//using namespace std;
//int n, m;
//int q;
//typedef pair<int, int> pll;
//const int N = 2e3 + 10;
//vector<pll>e[N];
//int dist[N];
//bool st[N];
//int cnt[N];
//bool sf()
//{
//    memset(cnt , 0 , sizeof cnt);
//    memset(st , 0 , sizeof st);
//    queue<int> q;
//    memset(dist, 0x3f, sizeof dist);
//    dist[1] = 0;
//    q.push(1);
//    st[1] = true;
//    while (q.size())
//    {
//        int u = q.front();  q.pop();
//        st[u] = false;
//        for (auto h : e[u])
//        {
//            int y = h.first; int z = h.second;
//            
//            if (dist[u] + z < dist[y])
//            {
//                dist[y] = dist[u] + z;
//                cnt[y] = cnt[u] + 1;
//                if (cnt[y] > n) return true;
//                if (!st[y])
//                {
//                    q.push(y);
//                    st[y] = true;
//                }
//            }
//        }
//    }
//
//    return false;
//}
//int main()
//{
//    cin >> q;
//    while (q--)
//    {
//        for (int i = 1; i <= n; i++)
//            e[i].clear();
//        cin >> n >> m;
//        for (int i = 1; i <= m; i++)
//        {
//            int x, y, z;
//            cin >> x >> y >> z;
//            e[x].push_back({ y,z });
//            if (z >= 0) e[y].push_back({ x,z });
//        }
//        if (sf())
//            cout << "YES" << endl;
//        else cout << "NO" << endl;
//           
//    }
//    return 0;
//}


//#include<iostream>
//#include<cstring>
//#include<vector>
//#include<queue>
//using namespace std;
//int n, m;
//typedef pair<int, int> pll;
//const int N = 1e3 + 10;
//vector<pll> e[N];
//vector<pll>fe[N];
//int dist[N];
//bool st[N];
//priority_queue<pll, vector<pll>, greater<pll>> q;
//int dj()
//{
//    memset(dist , 0x3f , sizeof dist);
//    dist[1] = 0;
//    q.push({ 0,1 });
//
//    while (q.size())
//    {
//        int u = q.top().second;  q.pop();
//        if (st[u]) continue;
//        st[u] = true;
//        for (auto h : e[u])
//        {
//            int v = h.first;  int w = h.second;
//   
//            if (dist[u] + w < dist[v])
//            {
//                
//                dist[v] = dist[u] + w;
//                q.push({dist[v],v});
//            }
//        }
//    }
//    int ret = 0; 
//    for (int i = 1; i <= n; i++)
//        ret += dist[i];
//    return ret;
//}
//int fdj()
//{
//    memset(dist, 0x3f, sizeof dist);
//    memset(st, 0, sizeof st);
//    dist[1] = 0;
//    q.push({0,1});
//    while (q.size())
//    {
//        int u = q.top().second; q.pop();
//        if (st[u]) continue;
//        st[u] = true;
//        for (auto h : fe[u])
//        {
//            int v = h.first;  int w = h.second;
//
//            if (dist[u] + w < dist[v])
//            {
//                dist[v] = dist[u] + w;
//                q.push({ dist[v],v });
//            }
//        }
//    }
//    int ret = 0;
//    for (int i = 1; i <= n; i++)
//        ret += dist[i];
//    return ret;
//}
//
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= m; i++)
//    {
//        int x, y, z; cin >> x >> y >> z;
//        e[x].push_back({y,z});
//        fe[y].push_back({x,z});
//    }
//    cout << dj() + fdj() << endl;
//    return 0;
//}


//#include<iostream>
//#include<cstring>
//#include<vector>
//#include<queue>
//#include<cmath>
//using namespace std;
//typedef pair<double, double> pll;
//int n, m; int s, t;
//const int N = 110 ;
//vector<pll>e[N];
//double dist[N];
//bool st[N];
//pll node[N];
//void dj()
//{ 
//    priority_queue<pll, vector<pll>,greater<pll>> q;
//    for (int i = 1; i <= n; i++)
//        dist[i] = 1e10;
//    dist[s] = 0.0;
//    q.push({0,s});
//    while (q.size())
//    {
//        int u = q.top().second; q.pop();
//        if (st[u]) continue;
//        st[u] = true;
//        for (auto h : e[u])
//        {
//            int v = h.first; double w = h.second;
//            if (dist[u] + w < dist[v])
//            {
//                dist[v] = dist[u] + w;
//                q.push({ dist[v]  , v });
//            }
//        }
//            
//    }
//}
//int main()
//{
//    cin >> n ;
//    for (int i = 1; i <= n; i++)
//        cin >> node[i].first >> node[i].second;
//    cin >> m;
//    for (int i = 1; i <= m; i++)
//    {
//        int x, y; cin >> x >> y;
//        int dx = node[x].first - node[y].first;
//        int dy = node[x].second - node[y].second;
//        double w = sqrt(dy * dy + dx * dx);
//        e[x].push_back({ y,w });
//        e[y].push_back({x,w});
//    }
//    cin >> s >> t;
//    dj();
//
//    printf("%.2lf\n" ,dist[t]);
//    return 0;
//}


// 


//#include<iostream>
//#include<cstring>
//#include<queue>
//#include<vector>
//using namespace std;
//int n, m;
//const int N = 1e6, MOD = 100003;
//typedef pair<int, int> pll;
//vector<int>e[N];
//bool st[N];
//int dist[N];
//int dp[N];
//priority_queue<pll, vector<pll>, greater<pll>> q;
//void dj()
//{
//    memset(dist , 0x3f , sizeof dist);
//    dist[1] = 0;
//    dp[1] = 1;
//    q.push({0,1});
//    while (q.size())
//    {
//        int u = q.top().second; q.pop();
//        if (st[u]) continue;
//        st[u] = true;
//        for (auto v : e[u])
//        {
//           
//            if (dist[u] + 1 < dist[v])
//            {
//                dp[v] = dp[u];
//                dist[v] = dist[u] + 1;
//                q.push({ dist[v] , v });
//            }
//            else if (dist[u] + 1 == dist[v])
//                dp[v]= (dp[v]+dp[u])%MOD;
//        }
//    }
//}
//
//
//
//int main()
//{
//    scanf_s("%d %d" ,&n , &m);
//    for (int i = 1; i <= m; i++)
//    {
//        int x, y; scanf_s("%d %d", &x , &y);
//         e[x].push_back(y);
//        e[y].push_back(x);
//    }
//     dj();
// 
//     for (int i = 1; i <= n; i++)
//         printf("%d\n",dp[i]);
//    return 0;
//}


//#include<iostream>
//#include<cstring>
//using namespace std;
//const int N = 110;
//int n, m;
//int f[N][N];
//int main()
//{
//    cin >> n >> m;
//  
//    memset(f,0x3f , sizeof f);
//    for (int i = 1; i <= n; i++)
//        f[i][i] = 0;
//
//    
//        for (int j = 1; j <= m; j++)
//        {
//            int x, y, z; cin >> x >> y >> z;
//            f[x][y] = f[y][x] =  min(f[x][y], z);
//        }
//    
//
//    for (int k = 1; k <= n; k++)
//        for(int i = 1 ; i <= n ; i++)
//            for (int j = 1; j <= n; j++)
//                f[i][j] = min(f[i][j], f[i][k]+ f[k][j]);
//            
//    
//    for (int i = 1; i <= n; i++)
//    {
//
//        for (int j = 1; j <= n; j++)
//        {
//            cout << f[i][j] << " ";
//        }
//        cout << endl;
//    }
//
//    return 0;
//}



//#include<iostream>
//#include<cstring>
//using namespace std;
//const int N = 110;
//const int M = 1e4 + 10;
//int n, m;
//int f[N][N];  
//int path[M];
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= m; i++)
//        cin >> path[i];
//
//  
//    for(int i =1 ; i<= n ; i++)
//    for (int j = 1; j <= n; j++)
//    {
//        cin >> f[i][j];
//    }
//
//
//    for (int k = 1; k <= n; k++)
//        for (int i = 1; i <= n; i++)
//            for (int j = 1; j <= n; j++)
//                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
//
//    int ret = 0;  int prev = 1;
//    for (int i = 1; i <= m; i++)
//    {
//
//        ret += f[prev][path[i]];
//        prev = path[i];
//    }
//    cout << ret << endl;
//    return 0;
//}

//#include<iostream>
//#include<algorithm>
//using namespace std;
//string s1, s2;
//void cmp()
//{
//	int c1 = s1.size();
//	int c2 = s2.size();
//	if (c1 < c2)
//		swap(s1, s2);
//	else if (c1 == c2)
//		if (s1 < s2)
//			swap(s1, s2);
//
//}
//int main()
//{
//	string ret;
//	cin >> s1 >> s2;
//	cmp();
//	int cnt1 = s1.size() - 1;
//	int cnt2 = s2.size() - 1;
//	int tmp = 0;
//	while (cnt1 >= 0)
//	{
//		int x1 = 0, y1 = 0;
//		if (cnt1 >= 0)
//			x1 = s1[cnt1--] - '0';
//		if (cnt2 >= 0)
//			y1 = s2[cnt2--] - '0';
//		if (x1 < y1 + tmp)
//		{
//			ret += (x1 + 10 - y1 - tmp) + '0';
//			tmp = 1;
//		}
//		else
//		{
//			ret += (x1 - y1 - tmp) + '0';
//			tmp = 0;
//		}
//
//	}
//
//	cout << ret << endl;
//
// 	reverse(ret.begin(), ret.end());
//	while ( ret.size() > 1 && ret.back() == '0' ) ret.pop_back();
//	cout << ret << endl;
//
//	return 0;
//}


//#include<iostream>
//#include<algorithm>
//#include<string>
//using namespace std;
//string s1, s2;
//const int N = 4010;
//int a[N];
////int main()
////{
////	cin >> s1 >> s2;
////	int n1 = s1.size();
////	int n2 = s2.size();
////	reverse(s1.begin(), s1.end());
////	reverse(s2.begin(), s2.end());
////	string ret;
////	for (int i = 0; i < n1; i++)
////	{
////		for (int j = 0; j < n2; j++)
////		{
////			a[i + j] += ((s1[i] - '0') * (s2[i] - '0'));
////		}
////	}
////
////	int tmp = 0;
////	for (int i = 0; i <= n1 + n2; i++)
////	{
////		int d = tmp + a[i];
////		ret += (d % 10) + '0';
////		tmp = d / 10;
////	}
////
////	cout << ret << endl;
////	return 0;
////}
//
//int main()
//{
//    int a = ('1' - '0') * 0;
//    cout << a << endl;
//}




//#include<iostream>
//using namespace std;
//const int N = 5e3 + 10;
//int a[N][N];
//int f[N][N];
//int n, m;
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)
//    {
//        int x, y, z;
//        cin >> x >> y >> z;
//        x++; y++;
//        a[x][y] += z;
//    }
//    n = 5001;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= n; j++)
//        {
//            f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j];
//        }
//    }
//
//    int ret = 0;
//    m = min(n, m);
//    for (int i = m; i <= n; i++)
//    {
//        for (int j = m; j <= n; j++)
//        {
//            int x1 = i - m + 1;
//            int y1 = j - m + 1;
//            int d = f[i][j] - f[x1 - 1][j] - f[i][y1 - 1] + f[x1 - 1][y1 - 1];
//            ret = max(ret, d);
//        }
//    }
//    cout << ret << endl;
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//typedef long long ll;
//ll f[N]; int n, m;
//int path[N];
//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= m; i++)
//	{
//		cin >> path[i];
//	}
//	for (int i = 2; i <= m; i++)
//	{
//		if (path[i - 1] < path[i])
//		{
//			f[path[i - 1]]++;  f[path[i]]--;
//		}
//		else
//		{
//			f[path[i - 1]]--;  f[path[i]]++;
//		}
//	}
//	for (int i = 1; i < n; i++)
//		f[i] += f[i - 1];
//
//	ll ret = 0;
//	for (int i = 1; i < n; i++)
//	{
//		int a, b, c;  cin >> a >> b >> c;
//		ret += min(a * f[i], c + b * f[i]);
//	}
//
//	cout << ret << endl;
//	return 0;
//}

//#include<iostream>
//using namespace std;
//const int N = 1e6 + 10, M = 2e3 + 10;
//int n, m;
//int a[N];
//int st[M];
//int kind;
//
//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++) cin >> a[i];
//	int len = 2e3 + 10;  int retr = 0;   int l = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		st[a[i]]++;
//		if (st[a[i]] == 1)
//			kind++;
//		if (i - l >= m)
//		{
//			while (kind == m)
//			{
//				st[a[++l]]--;
//				if (st[a[l]] == 0) kind--;
//
//				if (i - l < len)
//				{
//					len = i - l;
//					retr = i;
//				}
//			}
//			
//		}
//
//	}
//
//
//	cout <<  retr - len << " " << retr << endl;
//	return 0;
//}

//#include<iostream>
//#include<cmath>
//#include<algorithm>
//using namespace std;
//const int N = 1e3 + 10;
//struct lei
//{
//	double l;
//	double r;
//}a[N];
//
//int n; 
//double r;
//
//bool cmp(lei &x1, lei& x2)
//{
//	return x1.l < x2.l;
//}
//int main()
//{
//	int cnt = 0;
//	while (cin >> n >> r)
//	{
//		
//		if (n == 0 && r == 0)  break;
//		cnt++;
//		int f = 0;
//
//			for (int i = 1; i <= n; i++)
//			{
//				double x, y;   cin >> x >> y;
//
//				if (y > r)
//					f = 1;
//				
//
//				double len = sqrt(r * r - y * y);
//				a[i].l = x - len;  a[i].r = x + len;
//
//			}
//			if (f == 1)
//			{
//				cout << "Case " << cnt << ": " << -1 << endl;
//
//			}
//			else
//			{
//
//				sort(a + 1, a + 1 + n, cmp);
//				int ret = 1;  double rr = a[1].r;
//				for (int i = 2; i <= n; i++)
//				{
//					double right = a[i].r;  double left = a[i].l;
//					if (rr >= left)
//					{
//						rr = min(rr, right);
//					}
//					else
//					{
//						ret++;
//						rr = right;
//					}
//				}
//
//
//				cout << "Case " << cnt << ": " << ret << endl;
//
//			}
//	}
//	return 0;
//}


//#include<iostream>
//#include<unordered_map>
//#include<algorithm>
//using namespace std;
//const int N = 1e7 + 10, M = 1e3 + 10;
//
//unordered_map<int, int> mp;
//struct node
//{
//	int l, r;
//}a[M];
//int d;
//int dist[M*2];
//int wall[N];
//int n, m;
//bool st[N];
//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= m; i++)
//	{
//		cin >> a[i].l >> a[i].r;
//
//		d++;  dist[d] = a[i].l;
//		d++; dist[d] = a[i].r;
//	}
//	sort(dist+1 , dist+1 + d);
//	int cnt = 0;
//	for (int i = 1; i <= d; i++)
//	{
//		int x = dist[i];
//		if (mp.count(x)) continue;
//		cnt++;
//		mp[x] = cnt;
//		cnt++;
//		mp[x + 1] = cnt;
//	}
//
//	for (int i = 1; i <= m; i++)
//	{
//		int x = mp[a[i].l];  int y = mp[a[i].r];
//		for (; x <= y; x++)
//		{
//			wall[x] = i;
//		}
//	}
//
//	int ret = 0;
//
//	for (int i = 1; i <= n; i++)
//	{
//		if (st[wall[i]] == false && wall[i] != 0)
//			ret++;
//		st[wall[i]] = true;
//	}
//
//	cout << ret << endl;
//	return 0;
//}


//#include<iostream>
//#include<string>
//using namespace std;
//string s;  int n;
//void check(string x)
//{
//	char a = x[0];
//	for (auto e : x)
//		if (a != e)
//		{
//			cout << "F";
//			return;
//		}
//	if (a == '1')
//		cout << "I";
//	else cout << "B";
//}
//void dfs(string ss)
//{
//	int sz = ss.size();
//	if (sz == 1)
//	{
//		if (ss[0] == '1')
//			cout << "I";
//		else cout << "B";
//			return;
//	}
//	dfs(ss.substr(0, sz / 2));
//	dfs(ss.substr(sz / 2, sz));
//
//	check(ss);
//}
//int main()
//{
//	cin >> n >> s;
//	dfs(s);
//	return 0;
//}


//#include<iostream>
//#include<algorithm>
//using namespace std;
//typedef long long ll;
//const int N = 5e5 + 10;
//int a[N];   int b[N];
//int n;
//ll merge(int l, int r)
//{
//    if (r <= l) return 0;
//    ll ret = 0;
//    int mid = (l + r) / 2;
//    ret += merge(l, mid);
//    ret += merge(mid + 1, r);
//
//    int cnt1 = l; int cnt2 = mid + 1; int i = l;
//    while (cnt1 <= mid && cnt2 <= r)
//    {
//        if (a[cnt1] <= a[cnt2])   b[i++] = a[cnt1++];
//        else
//        {
//            ret += mid - cnt1 + 1;
//            b[i++] = a[cnt2++];
//        }
//    }
//
//    while (cnt1 <= mid) b[i++] = a[cnt1++];
//
//    while (cnt2 <= r) b[i++] = a[cnt2++];
//    for (int j = l; j <= r; j++) a[j] = b[j];
//    return ret;
//
//}
//int main()
//{
//    cin >> n;
//    for (int i = 1; i <= n; i++) cin >> a[i];
//
//    cout << merge(1, n) << endl;
//    return 0;
//}

//#include<iostream>
//#include<vector>
//#include<cstdio>
//using namespace std;
//int n;
//vector<vector<int>> ret;
//vector<int> path;
//bool st[11];
//void dfs(int pos)
//{
//    if (path.size() == n)
//    {
//        ret.push_back(path);
//        return;
//    }
//
//    for (int i = 1; i <= n; i++)
//    {
//        if (!st[i])
//        {
//            st[i] = true;
//            path.push_back(i);
//            dfs(i+1);
//            path.pop_back();
//            st[i] = false;
//        }
//    }
//}
//int main()
//{
//    cin >> n;
//    dfs(1);
//    for (auto e : ret)
//    {
//        for (auto h : e)
//            printf("%5d",h);
//        printf("\n");
//    }
//    return 0;
//}


//#include<iostream>
//#include<cstring>
//using namespace std;
//const int N = 20;
//int T,n;
//int t[N], d[N], l[N];
//bool st[N];   int tm;
//bool dfs(int pos)
//{
//    if (pos >= n )
//        return true;
//
//    for (int i = 1; i <= n; i++)
//    {
//        if (!st[i]) 
//        {
//            int old = tm;
//           
//            if (tm <= t[i] + d[i])
//            {
//                tm = max(tm, t[i]) + l[i];
//            }
//            else
//                continue;
//
//            st[i] = true;
//            if (dfs(pos + 1))  return true;
//            st[i] = false;
//            tm = old;
//           
//        }
//    }
//
//    return false;
//}
//int main()
//{
//    cin >> T;
//    while (T--)
//    {
//        memset(st, 0, sizeof st);   
//        tm = 0;
//        cin >> n;
//        for (int i = 1; i <= n; i++)
//            cin >> t[i] >> d[i] >> l[i];
//        if (dfs(0)) 
//            cout << "YES" << endl;
//        else cout << "NO" << endl;
//    }
//    return 0;
//}


//#include<iostream>
//using namespace std;
//int a[9][9];
//bool col[9][10];
//bool row[9][10];
//bool kuai[4][4][10];
//bool dfs(int x , int y )
//{
//    if (y == 9)
//    {
//        x++;  y = 0;
//    }
//
//    if (x == 9)
//        return true;
//    if (a[x][y])
//        return dfs(x,y+1);
//
//    for (int i = 1; i < 10; i++)
//    {
//        if (!col[x][i] && !row[y][i] && !kuai[x / 3][y / 3][i])
//        {
//            col[x][i] = row[y][i] = kuai[x / 3][y / 3][i] = true;
//            a[x][y] = i;
//            if (dfs(x, y + 1)) return true;
//            a[x][y] = 0;
//                col[x][i] = row[y][i] = kuai[x / 3][y / 3][i] = false;
//
//        }
//    }
//    return false;
//}
//int main()
//{
//    for (int i = 0; i < 9; i++)
//        for (int j = 0; j < 9; j++)
//        {
//
//            cin >> a[i][j];
//            if (a[i][j])  
//                col[i][a[i][j]] = row[j][a[i][j]] = kuai[i / 3][j / 3][a[i][j]] = true;
//        }
//    dfs(0 , 0);
//    for (int i = 0; i < 9; i++)
//    {
//        for (int j = 0; j < 9; j++)
//            cout << a[i][j] << " ";
//        cout << endl;
//    }
//    return  0;
//}


//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 20;  int ret = 20;
//typedef long long ll;
//ll sum[N];  bool st[N];
//int n, w;  
//int a[N];  int cnt;
//bool cmp( int x , int y)
//{
//    return x > y;
//}
//void dfs(int pos )
//{
//    if (cnt > ret)
//        return;
//    if (pos == n+1)
//    {
//        ret = cnt;
//        return;
//    }
//
//    for (int i = 1; i <= cnt; i++)
//    {
//        if (sum[i] + a[pos] > w) continue;
//        sum[i] += a[pos];
//        dfs(pos+1);
//        sum[i] -= a[pos];
//    }
//
//    cnt++;
//    sum[cnt] += a[pos];
//    dfs(pos+1);
//    sum[cnt] -= a[pos];
//    cnt--;
//}
//int main()
//{
//    cin >> n >> w;
//    for (int i = 1; i <= n; i++) cin >> a[i];
//    sort(a+1 , a+1+n , cmp);
//    dfs(1);
//
//    cout << ret << endl;
//    return 0;
//}


//#include<iostream>
//using namespace std;
//const int N = 1e4;
//int t, p; 
//char f[N][N];
//char dfs(int x , int y)
//{
//    if (f[x][y])  return f[x][y];
//    f[x][y] = '3';
//    if (x == 0) return f[x][y] = '1';
//    if (y == 0) return f[x][y] = '2';
//    return f[x][y] = dfs((x+y) % p, ((x + y) % p +y) % p);
//}
//int main()
//{
//    cin >> t >> p;
//    while (t--)
//    {
//        int x, y; cin >> x >> y;
//        char ret = dfs(x,y);
//        if (ret == '3') cout << "error" << endl;
//        else cout << ret << endl;
//    }
//    return 0;
//}


//#include<iostream>
//using namespace  std;
//const int N = 110;
//int mp[N][N];
//int f[N][N];
//int n, m;
//int dx[] = {0,1,0,-1};
//int dy[]= {1,0,-1,0};
//int dfs(int x , int y)
//{
//    if (f[x][y]) return f[x][y];   
//
//    int len = 0;
//    for (int i = 0; i < 4; i++)
//    {
//        int xx = x + dx[i];  int yy = y + dy[i];
//        if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && mp[xx][yy] < mp[x][y])
//        {
//           len = max(  len , dfs(xx, yy));
//        }
//
//    }
//    
//    return f[x][y] = len+1;
//}
//int main()
//{
//    cin >> n >> m;
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//            cin >> mp[i][j];
//    int ret = 1;
//
//    for (int i = 1; i <= n; i++)
//        for (int j = 1; j <= m; j++)
//             ret = max( ret,dfs(i,j));
//    
//    cout << ret << endl;
//    return 0;
//}


//#include<iostream>
//#include<cstring>
//#include<unordered_map>
//#include<queue>
//using namespace std;
//unordered_map<string, int> mp;
//string s;
//int dx[] = {1,0,-1,0};
//int dy[] = {0,1,0,-1};
//int ret;
//string ss = "123804765";
//void bfs()
//{
//    queue<string> q;   
//    q.push(s);  mp[s]++;
//    while (q.size())
//    {
//        int sz = q.size();  ret++;
//        while (sz--)
//        {
//            string xx = q.front();  q.pop();
//            int num = xx.find('0');
//            int i = num / 3;  int j = num % 3;
//            for (int k = 0; k < 4; k++)
//            {
//                int x = dx[k] + i;   int y = dy[k] + j;
//                if (x >= 0 && x < 3 && y >= 0 && y < 3)
//                {
//                    string sb = xx;   swap(sb[num] , sb[x*3+y]);
//                    if (mp.count(sb)) continue;
//                    mp[sb]++;
//                    q.push(sb);
//                    if (sb == ss)
//                    {
//                        
//                        return;
//                    }
//                
//                }
//            }
//        }
//    }
//}
//int main()
//{
//    cin >> s;
//    bfs();
//    cout << ret << endl;
//    return 0;
//}


//#include<iostream>
//using namespace std;
//typedef long long ll;
//ll a, b, c, k;
//int t;   
//void dfs(ll aa, ll bb, ll cc, ll kk)
//{
//    if (kk == 0)
//    {
//        cout << aa << " " << bb << " " << cc << endl;
//        return;
//    }
//    ll aaa = (bb + cc) / 2;
//    ll bbb = (aa + cc) / 2;
//    ll ccc = (aa + bb) / 2;
//    dfs(aaa, bbb, ccc, kk-1);
//}
//int main()
//{
//    cin >> t;
//    while (t--)
//    {
//        cin >> a >> b >> c >> k;
//        dfs(a, b, c, k);
//    }
//    return 0;
//}


#include<iostream>
#include<vector>
using namespace std;
int n,k; 
const int N = 1e5 + 10;
int a[N]; 
long long ret = 1e18;
vector<int> path;
vector<int> path1;
bool st[N];
void check()
{
    long long sum = 0;
    for (int i = 1; i < k; i++)
    {
        sum += abs(path1[i]*path1[i]-path1[i-1]*path1[i-1]);
    }
    ret = min(ret , sum);
}
void dfs2()
{
    if (path1.size() == k)
    {
        check();
        return;
    }
    for (int i = 0; i < k; i++)
    {
        if (st[i]) continue;
        st[i] = true;
        path1.push_back(path[i]);
        dfs2();
        path1.pop_back();
        st[i] = false;
    }
}
void dfs1(int pos)
{
    if (path.size() == k )
    {
        dfs2();
        return;
    }
    for (int i = pos; i <= n; i++)
    {
        path.push_back(a[i]);
        dfs1(i+1);
        path.pop_back();
    }
}
int main()
{
    cin >> n >> k;

    for (int i = 1; i <= n; i++)
        cin >> a[i];
    dfs1(1);
    cout << ret << endl;
    return 0;
}